4 ms·
I'm pretty sure your second definition is an upper bound (big-O) and the first definition is a lower bound (big-Omega). EDIT: adding a link to the wikipedia ar
by sonoffett 16y ago
I'm pretty sure your second definition is an upper bound (big-O) and the first definition is a lower bound (big-Omega).
EDIT: adding a link to the wikipedia article defining Big-O and Big-Omega: http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation
- cma 16y agoYeah I screwed that up, what I meant to refer to is this: >It is not contradictory however, to say that the worst-case >running time of insertion sort is [Big Omega](n^2), >since there exists an input that causes the algorithm >to take [Big Omega](n^2) time. >Introduction to Algorithms, 2nd Edition, p 46