Omega Directive

Recall from Week 2 that an upper bound on the running time of an algorithm can be described with asymptotic notation using O, pronounced "big O." We described the running time of linear search, for instance, as being in O(n), insofar as it might take as many as n steps to find one element among n in a list in the worst case (if that element happens to be at the end of the list).

It turns out that you can similarly describe a lower bound on the running time of an algorithm with asymptotic notation using Ω, pronounced "big omega." Indeed, we might describe the running time of linear search as also being in Ω(1), since, in the best case, it might only take one step (or, at least, a constant number of steps) to find some element among n in a list (if that element happens to be at the start of the list).

If the upper bound and lower bound on the running time of an algorithm happen to be the same, you can actually describe both together with asymptotic notation using ϴ, pronounced "theta." For instance, the implementation of isupper in C is in both O(1) and Ω(1) and, therefore, ϴ(1), since, no matter the char that you pass to it, it needs only a constant number of steps to check if that character is capitalized.

Answer the below in omega.md.

Questions

  1. (2 points.) Whereas bubble sort is in O(n2) and Ω(n), selection sort is in O(n2) and Ω(n2). Why is selection sort not also in Ω(n)?

  2. (2 points.) Merge sort, meanwhile, is in Ï´(n log n). In no more than two sentences in your own words, why?

  3. (2 points.) Why is the implementation of strlen in C necessarily in Ï´(n)?

  4. (2 points.) It turns out that the implementation of len for list in Python is in Ï´(1). Even if a list has n elements, len can determine its length in constant time. Why might that be?

  5. (2 points.) How does isupper in C, declared in ctype.h, likely determine in constant time whether a char is indeed capitalized?

Debrief

  1. Which resources, if any, did you find helpful in answering this problem’s questions?

  2. About how long, in minutes, did you spend on this problem’s questions?