Big O Notation: Using not-boring math to measure code's efficiency

Re:Big O Notation: Using not-boring math to measure code's e... by triplenineteen on Friday September 19, 2014 @08:51PM (#8343271)

> But to be more specific we could say this is worst case O(n) and best case O(1) runtime.

Those should really say θ(n) and θ(1).

[ Parent | on HN ]

Re:Big O Notation: Using not-boring math to measure code's e... by marcosdumay on Friday September 19, 2014 @08:59PM (#8343295)

That first one should be a big O.

[ Parent | on HN ]

Re:Big O Notation: Using not-boring math to measure code's e... by triplenineteen on Friday September 19, 2014 @09:24PM (#8343365)

Hmm. Big O already encompasses "at worst".

Theta is the notation for a single case, be it the worst case, the best case, one run of a randomized algo, etc.

At least that is my understanding.

[ Parent | on HN ]

Re:Big O Notation: Using not-boring math to measure code's e... by ephemeralgomi on Friday September 19, 2014 @09:30PM (#8343380)

Big O is an upper bound, little o is a lower bound. Big theta means both an upper and lower bound.

[ Parent | on HN ]