0
$\begingroup$

On the course material I am following we have been given an explanation for theta as being when omega and Oh 'sandwich' the run time, so it is bounded between the two values, at least I think this is how it is explained based on my interpretation.

So I was surprised to then find this as I have gotten further through the course:

Given the worst case running time for MAX-HEAPIFY - Ө(lgn), what do you think is the best case for MAX-HEAPIFY and what is the running time for the best case?

Answer:

The best case is that heap property is already in place so the time cost is constant Ө(1)

I dont understand how the theta notation can be used for both values, can someone explain this to me? When I think of the graph used to help me understand theta it might have O(1) as the 'lower bound' and O(log n) as the upper bound and the functions runtime would be somewhere between these values (is this correct?), but why is it o.k to say the worst case run time is THETA(log n) and the best case is THETA(1)? Why would they not use O for the upper and Omega for the lower?

I am still really confused about when I should O or Theta or Omega to describe something. I have read loads of posts and blogs about this and it still doesn't seem to sink in properly for me.

$\endgroup$
0