Back to General and Gameplay Programming

How to correctly pronounce big-oh notation?

General and Gameplay Programming Programming

Started by GDKnight December 05, 2005 01:03 AM

31 comments, last by GameDev.net 18 years, 4 months ago

684

December 06, 2005 03:49 PM

Quote:Original post by smitty1276
And regardless, it still doesn't answer my question of why Trap said mergesort was O(2^n). I suppose he just mistyped.

Because it is:
1) Definition of big-oh: it is O(2^n) if and only if there exist numbers x0 and M such that |f(n)| ≤ M |2^n| for n > x0.
2) Plug in f(n)=n*log(n)
3) Set M=1 and x0=1 and the prove n*log(n) ≤ 2^n for n>1 by induction
4) You have proven mergesort to be O(2^n)

kSquared

1,356

December 06, 2005 05:06 PM

Loose, non-rigorous recap of asymptotic notations for anyone who's still confused:

-- f ∈ O(g) means "f has order at most g"; e.g. 5xk ∈ O(xk) but ∉ O(1).
-- f ∈ o(g) means "f has order less than g"; e.g. 5xk ∈ o(6xk) but ∉ o(xk).
-- f ∈ Θ(g) means "f has order g"; x4 + x2 ∈ Θ(x4) but ∉ Θ(x5) and ∉ Θ(x3).
-- f ∈ ω(g) means "f has order greater than g".
-- f ∈ Ω(g) means "f has order at least g".

- k2"Choose a job you love, and you'll never have to work a day in your life." — Confucius"Logic will get you from A to B. Imagination will get you everywhere." — Albert Einstein"Money is the most egalitarian force in society. It confers power on whoever holds it." — Roger Starr{General Programming Forum FAQ} | {Blog/Journal} | {[email=kkaitan at gmail dot com]e-mail me[/email]} | {excellent webhosting}

Anonymous

December 06, 2005 08:26 PM

Quote:Original post by smitty1276
I understand you're point, but that doesn't make the first one correct in the sense that it is the true asymptotic upper bound of the function, only in the sense that the algorithm will run in less time. But in that sense their are an infinite number of upper bounds. There is only one REAL upper bound.

Mathematically speaking, you're talking about a set's least upper bound. Sometimes an upper bound which isn't the least upper bound is useful. Consider a quick proof that the arithmetic mean of a and b is between a and b.

WOLOG assume a g(n) forall n. Then, for some n_0 we have
A_c f(n_0) = B_c g(n_0)
You should use B when n > n_0, A when n <

How to correctly pronounce big-oh notation?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

How to correctly pronounce big-oh notation?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines