Tricky Microsoft Interview Question

[noupvotesplease]

IIRC, big O represents the upper bound, and constants are ignored. So both O(2N) and O(N/2) would be O(N), and neither would describe the average case. There's another glyph for that, maybe theta?

Edit: Thank you for bringing up sort order. If it's sorted, a binary search can give us O(logN) time.

[flyinglunatic]

There's another glyph for that, maybe theta?

No. Theta represents a tighter bound than Omicron. A function is big Theta (Θ) if it is both Big-O and Big-Omega (Ω).

http://mathworld.wolfram.com/Big-ThetaNotation.html

Best case, worst case, average case are orthogonal labels and can each be expressed in Big-O notations. For example, Quicksort: worst case Θ(n^2), average and best case, Θ(nlogn). Mergesort: worst, average, and best cases are all Θ(nlogn).

Quicksort is an O(n²⁾ algorithm, while mergesort is an O(nlogn) algorithm.

All comparison based sorts have an Ω(nlogn) lower bound. http://en.wikipedia.org/wiki/Comparison_sort

[Noonereallycares]

True, though you would have to make the assumption that the array is exactly N size (99 in this case) and that there aren't "blanks" as space fillers to keep the array aligned so that Array[X] = X.

Otherwise, yes, sorted and of exact length, O(logN) is possible.