Question

What is the big-Ω (best-case) running time of each of the following? Briefly justify your answers. You should reference the optimal algorithm for each problem.

(a) (2 points) Finding the max of a sorted list

(b) (2 points) Finding the median (middle number) of a sorted list of odd length

(c) (2 points) Finding the range of an unsorted list

(d) (2 points) Finding out if a list of strings has duplicates

(e) (2 points) Finding the square root of a number that is a perfect square

Answer 1

(a) (2 points) Finding the max of a sorted list If the array is sorted the max element is always present at either at index 0 (in ascending order) or at last(descending order). We can directly find it in constant time. Best Case Time Complexity: O(1)

(b) (2 points) Finding the max of a sorted list If the array is sorted list of odd length median is always present at middle of the array which will be found by array [ len_of_arr / 2 ] It takes only a constant time. Best Case Time Complexity: O(1)

(c) (2 points) Finding the range of an unsorted list. To find the range of an unsorted list we have to traverse from begging to end and find the min and max value of list. This is how it looks like. range(arr){ min = arr [0] max = arr [0] n = len(arr) for i=1 to n{ if(arr[i]<min){ min = arr[i] } if(arr[j]> max){ max = arr[j] } } return [min,max] } Since we have to traverse until end the t.c would be O(n) Best case time complexity: O(n)

e) (2 points) Finding the square root of a number that is a perfect square Let 's' be the answer. We know that 0 <= s <= x. Consider any random number r. If r*r = x If r*r > x, s < r. Approach :: 1) Start with ‘start’ = 0, end = ‘x’, 2) Do following while ‘start’ is smaller than or equal to ‘end’. a) Compute ‘mid’ as (start + end)/2 b) compare mid*mid with x. c) If x is equal to mid*mid, return mid. d) If x is greater, do binary search between mid+1 and end. In this case, we also update ans (Note that we need floor). e) If x is smaller, do binary search between start and mid int floorSqrt(int x) { // Base cases if (x == 0 || x == 1) return x; int start = 1, end = x, ans; while (start <= end) { int mid = (start + end) / 2; if (mid*mid == x) return mid; if (mid*mid < x) { start = mid + 1; ans = mid; } else{ end = mid-1; } } return ans; } IT is almost similler to Binary Search Best Case Time Complexity : O(Log N)