I am still having a hard time understanding what the WORST CASEtime complexity o

Question

I am still having a hard time understanding what the WORST CASEtime complexity of (g(n)) means. I know that if f(n) =(g(n)) then c f(n) >= g(n) for all n >= some n0 is alower bound. I don't, however, understand what this means interms of WORST CASE time complexity. P 46, section aftertheorem 3.1  in CLRS says "It is not a contradiction tosay the WORST CASE running time of insertion sort is(n2), since there exists an input that causes thealgorithm to take (n2) time." Sinceinsertion sort is O(n2), I don't get this. Doesthis mean WORST CASE time complexity of (n2) isalso an upper bound?

Explanation / Answer

//Hope this will help you. In general, Insertion sort lies between (n) and O(n2). This isthe case for any input sequence. But that line is talking about only worstcase which will always be (n2) { it can't be greater than n2or less than n2 }. So it is notcontradiction if we say it is (n 2) inworst case.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.