Note: we are looking for the best possible big-Oh bound as a function of the size of the input, n.
Note: we are looking for the best possible big-Oh bound as a function of the size of the input, n. The maximum subsequence sum problem can be solved in this time using an algorithm developed by Kadane. By looping from "n over 2" to 1 and sinking keys down, building a binary heap from an unsorted array can be shown to take this much time. From the master theorem, this is the running time of a program described by the recurrence T(n) = 4T(n/4) + 1 ["T of n equals 4 T of n over 4 plus 1"]. This is the running time of the conquer step of (*) merge sort and, contrary to popular belief, this is actually the worst-case time for a lookup in a hash map. This is the worst-case time to search for an element in a standard binary search tree, and this is the best case bound for any sorting algorithm. For 10 points, give the time needed to search for a specific element in an array.
Note: we are looking for the best possible big-Oh bound as a function of the size of the input, n.
O(n) [or big-Oh of n or linear time; accept big-Oh of [any linear function of n]; accept big-Theta of n or of [any linear function of n]; do not accept any “little-Oh”, “little-Omega”, or “big-Omega” answers]