CSC301 Data Structures and Algorithm

Assignment 1- Complexity Analysis

1. An array A contains n integers taken from the interval [0,4n], with repetitions

allowed. Describe an efficient algorithm for determining an integer value k that

occurs the most often in A. What is the running time of your algorithm?

2. An array A contains n?1 unique integers in the range [0,n?1], that is, there is one

number from this range that is not in A. Design an O(n)-time algorithm for finding

that number. You are allowed to use additional space besides the array A itself

3. In steps, find the computational complexity of the following loops:

(i) for ( c = 1, i = 1 ; i <= n ; i *= 2) for (j =1 ; j <= n ; j++) c++; (ii) for (cc = 1, i = 1 ; i <= n ; i *= 2) for (j = 1; j <= i ; j++) cc++;