Algorithm – the large O and Ω of the worst-case running time are the best cases, but why do you sometimes use Ω in the worst case?

I'm confused. I think you use big O runtime in the worst case. Ω is the best case? Can anyone explain?

Not (LG n) the best case? And (NLG n) is the worst case? Or did I misunderstand something?

Editor: No, it's not homework I'm practicing. There's a key to the answer. I'm confused http://www-scf.usc.edu/ ~csci303/cs303hw4solutions. Pdf question 4 (6.2 – 6)

Editor 2: so I misunderstood that it's not about big O and Ω?

Solution

It is important to distinguish between cases and boundaries

Best, average and worst are common situations when analyzing algorithms

The upper (O, O) and lower (omega, omega) and theta are the common boundary of the function

When we say "the worst-case time complexity of algorithm x is O (n)", we say that when we limit the input to the worst-case input, the function representing the performance of algorithm x is asymptotically Limited from above by some linear function You can say the lower limit of the worst-case input; Or the upper or lower limit of average or best case behavior

Case= Binding In other words, "the worst upper layer" and "the best upper layer" are quite sensible measures... They provide absolute limits for algorithm performance This does not mean that we cannot talk about other indicators

Edit to reply to your updated questions:

This question requires you to prove that omega (LG n) is the lower limit of worst-case behavior In other words, when the algorithm does as much work on a class of inputs as possible, its workload increases asymptotically at least as fast as (LG n) So your steps are as follows: (1) determine the worst case of the algorithm; (2) Find the lower bound of the algorithm runtime on the input belonging to the worst case

The following is a schematic diagram of a linear search:

In the worst case of linear search, the target item is not in the list, and all items in the list must be checked to determine this Therefore, the lower bound of the worst case complexity of the algorithm is O (n)

Important note: for a large number of algorithms, the complexity in most cases will be limited from top to bottom by a set of general functions Theta is bound to apply So, anyway, you probably won't get Omega's answer, not o