Re:Computer Scientists Make Progress on Math Puzzle
by amichail on Thursday October 28, 2010 @11:34AM
(#1843277)
You could always say the lower bound is zero or some very small function. That's pointless and is not better in any sense.
[ Parent
| on HN ]
Re:Computer Scientists Make Progress on Math Puzzle
by cma on Thursday October 28, 2010 @12:19PM
(#1843504)
There are two notions of lower bound:
lower bound like you are talking about (the function always takes longer than this to run for an input of size n)
lower bound across all inputs of size n (the function never runs faster than this, given any possible input of size n)
The two are different
Re:Computer Scientists Make Progress on Math Puzzle
by sonoffett on Thursday October 28, 2010 @01:12PM
(#1843780)
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
Re:Computer Scientists Make Progress on Math Puzzle
by cma on Thursday October 28, 2010 @07:52PM
(#1845464)
Yeah 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