Quote:Original post by UknowsI
Quote:Original post by Limitz
Quote:Original post by UknowsI
Quote:Original post by _swx_
They are still O(n^n) ;)
From http://en.wikipedia.org/wiki/Big-O
"More precisely, it is used to describe an asymptotic upper bound"
"the O notation is commonly employed to describe an asymptotic tight bound, but tight bounds are more formally and properly denoted by the Θ (big Theta) "
Algorithms such as quicksort and binary search do not have an asymptotically tight bound (Θ) if I remember correctly. So the notation he is refering to is probably the slowest growing Big O notation possible. Does this have a formal name?
Shouldn't you use Big Omega for that, like, finding the function that is at least OMEGA(n^n)
I'll give you an example though. With Quicksort the largest possible Omega is Omega(n log n) while the smallest possible O is O(n^2). What most people are interested in is the smallest possible O, which is different, and larger than the largest possible Omega.
With this much confusion over Big O notation I really wonder how a discussion about NP-Hard vs NP-Complete vs NP-problems would end ;)
That would be quite a discussion with a Huge running time probably :)
EDIT: (still hoping i will solve one of the rsa challenge numbers any day soon :p )
My Introduction to Algorithms book by Cormen, Leiserson, Rivest and Stein (a must have for every programmer) , only assumes that O(whatever) should be the worst running time of an algorithm, and use small o if it is not asymptotically bound. However, i couldn't find any standards what so ever...