Geek asks and answers

Big O for worst-case times and Ω for best cases, but why is Ω sometimes used in the worst cases?

I'm confused, I thought you were using Big O for the worst running time, and Ω for the best case? Can someone explain?

And no (lg n) best case? and (nlg n) is the worst case? Or am I not understanding something?

Show that the worst-case Max-Heapify run time on a heap of size n is Ω (log n). (Hint: for a heap with n nodes, give node values ​​that make Max-Heapify call recursively on each node along the path from root to leaf.)

Edit: no, this is not homework. im a practitioner, and this one has a response key that I confused. http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf Problem 4 (6.2 - 6)

Edit 2: So, I misunderstood the question is not about Big O and Ω?

+5
source share
3 answers

It is important to distinguish between case and rating.

Best, medium, and worst are common cases of interest in analyzing algorithms.

Upper (O, o) and lower (Omega, omega) together with Theta are common boundaries of functions.

When we say: “Algorithm X with worst case time complexity is O (n)”, we say that the function that represents the performance of Algorithm X when we restrict the input data for the worst case inputs is asymptotically bounded from above by some linear function. You could talk about the bottom line of entering the worst case; or the upper or lower bound of the average or best case behavior.

!= . , " " " " - ... . , .

, :

, Omega (lg n) . , ​​ , , , , , (lg n), . , : (1) ; (2) , .

, :

, , . O (n).

: . , . , , Omega, O, .

+14

Big O , , , Ω , , .

, , , lg (n).

-1

O is the upper limit (i.e. the worst case) Ω is the lower limit (i.e. the best case)

The example says that in the worst input for max-heapify (I think the worst input is the reverse order of input) the runtime complexity should be (at least) lg n. Therefore, Ω (log n), since this is the lower limit of the complexity of execution.

-1
source

More articles:


All Articles