Time complexity - understanding big-Theta

Question

I'm currently taking algorithms and data structure. After nearly two months of studying, I still find time complexity extremely confusing.

I was told (by my professor) that if I big-omega and big-O of some program aren't equal, big-theta doesn't exist.

I now literally question everything I've learned so far. I'll take BubbleSort as an example, with big-omega(n),big-theta(n^2) and big-O(n^2). Big-theta indeed does exist (and it makes sense when i analyze it).

Can anyone explain to me whether my professor is wrong or perhaps I misunderstood something?

Answer 1

There exists big O, Big ?, and Big ?.

1. O is the upper bound
2. ? is the lower bound
3. ? exists if and only only if O = ?

In essence, Big-O is the most useful in that it tells us the WORST a function can behave.

Big-? indicates the BEST it can behave.

When WORST = BEST, you get ALWAYS. That's Big-?. When a function always behaves the same.

Example (optimized bubble sort, then has boolean flag for when a swap occurs):

bubbleSort() ? ?(n)
bubbleSort() ? O(n^2)

This means, the best bubble sort can do is linear time. But, in the worst case, it DEGRADES to quadratic time. Reason, on a pre-sorted list, bubble sort behaves quiet well, as it does one loop through the list (n iterations) and exits. Whereas, on a list in descending order, it would do roughly n(n-1)/2 iterations, which is proportional to n^2. Depending on the input, bubble sort behaves DRASTICALLY (different order or magnitude) differently.

Whereas:

mergeSort() ? ?(n * log n)
mergeSort() ? O(n * log n)

This means, in the best case merge sort is in n * log n time, and in the worst case. It is ALWAYS n * log n. That is because, no matter what the input is, merge sort will always recursively divide the list in half-size sub-arrays, and put them back together once each sub-array is of size 1. However, you can only break something in half so many times (log2(n)) times. Then, the merge() routine that is O(n) is called once per mergeSort() which occurs log2(n) times. So, for ALL executions of mergeSort() you get n * log2(n).

Therefore we can make a STRONGER statement and say that:

mergeSort() ? ?(n * log n)

We can only make such definitive statements (use big theta) if the runtime of a function is bounded above and below by functions of the exact same order of magnitude.

How I remember it:

? is an end all be all, whereas O, and ? are simply limits.

Answer 2

lets take this problem in 2 ways:

First Way:

we say that O(bubble sort) is O(n^2) and ?(bubble sort) is ?(n). The above statement holds true because, when the elements are laid down in array in sorted or almost sorted manner then bubble sort will have an equation of running time in form of -> an + b, where a and b are constants (a is positive).

but when elements are laid down in array in not so sorted manner or very unsorted manner, then the running time will be in form -> an^2 + bn + c. where a,b,c are constants (a is positive).

thus, bubble sort ? O(n^2) and bubble sort ? ?(n).

PS: differentiating what will constitute to almost sorted manner and what will constitute to not so sorted manner is talk for another day, but you can google it you will find it easily.

Now, Second way:

Rather than taking Big-O and Big-? of bubble sort we divide bubble sort into its worst case and best case.

now we say what is Big-O of worst case of bubble sort we get. O(n^2), i.e, worst case of bubble sort ? O(n^2).

but now since we have specified that we are dealing with only worst case then Big-? of worst case of bubble sort will also be ?(n^2).

Thus in this case ?(n^2) exists. because O = ?.

Using similar approach, we can see that the best case of bubble sort will have ?(n).

Note: worst case will be in form: an^2 + bn + c. and best case will be in form: an + b.

-------------------------------------------------------

In second way we bifurcated the worst case and best case then only we were able to reach to ? notations for both the cases.

Bubble sort as a whole had different polynomial equations as its running time with different degree that is why it did not have a ? notation.