1. Arrays and Heaps (8 points)

(1) Suppose you wanted to create an algorithm to find the number of elements k in an array, A, of n distinct elements. Specifically, describe efficient algorithms to solve this problem when A is the following data structures.

(a) (1 points) Unsorted array

(b) (1 points) Sorted array

(c) (2 points) Max-heap

(2) Analyze the runtime of your three algorithms from the previous part:

(a) (1 points) Unsorted array

(b) (1 points) Sorted array

(c) (2 points) Max-heap