Computer Science Majors: Big Omega Notation Help!

[Epon]

I understand how to analyze algorithms with Big-O and Big-Theta, but Big-Omega tosses me for a loop.

Big-O deals with worst case scenerios (higher bounds)
Big-Theta deals with the average case scenerios (tight bounds)
Big-Omega deals with best case, right? How does one figure this out?

From what I know, Big-O is simply the highest order of magnatude, for example:

T(n) = 4n^3+3n, Big-O(n^3)...... right?

[Sz]

You're close, but slightly off on your definition.

Big-O is the upper bound.
Big-Omega is the lower bound.
Big-Theta is the tight bound -- more specifically, the exact answer.

For casual purposes, they're almost interchangable. Big-O and Big-Theta especially -- almost all techniques for giving you a decent upper bound will give you the tight bound.

What Big-O and Big-Omega can be and are used for, though, is proving the Big-Theta of functions -- nasty ones especially.


For example, say we have:

T(n) = 2T( ceiling[n/2] ) + O(n)
-if it were 2T(n/2) + O(n), it'd be Theta(nlogn) trivially. However, the ceiling blows that up. But you can say T(n) = Omega(nlogn)

Then we can say that T(n) < 2T(n/2 +1) + O(n), and find the Big-O runtime, which will also be nlogn (this one is a pain to solve, IIRC). So since we get both to the same factor, we can say T(n) = Theta(nlogn).

Basically, Big-O and Big-Omega are clever constructs to simplify ridiculously weird runtimes into decently readable ones.

[Epon]

Okay, I got ya. Mind just answering this example then for me?

The cost function of an algorithm is T(n)<3n+1. What is the big-O, the big-Omega and the big-Theta for the algorithm?

Off the top of my head, wouldn't it's big-O be O(n)? Theta should be the same, too, right?

[Sz]

Given that the example is simple, I guess they could want specifics.

If it were a high level CS class we'd just plop down O(n) for the thing and be done with it. ;P

Anyway, your tight bound is Theta(3n) -- which is technically Theta(n), since the constant is almost irrelevant in theoretical CS. T(n) = O(n), beyond a shadow of a doubt. 4n is an upper bound ... 2n is a lower bound ...

I guess you could say:
Omega(2n)
O(4n)
Theta(3n)

But I don't even remember if that's the correct notation (to include the constant with the bound, I haven't done that in forever at least), and I need to emphasize that I have no idea if that's what whoever wants this ... wants.

[Epon]

So, let's swap that around a bit. Let's say it was T(n)=4n^2+n, then would they be:

O(4n^3).... or to be legit, O(n^3)
Omega(4n).... O(n)
Theta(n^2)?


And what's the deal when they give you, say, like what you gave in your original example... setting T(n) = 2T(n/2)+n I know that formula for figuring out nlogn and whatnots, but what's the diff between this and the example i gave above?

[Kulock]

"It's Showtime!"

Sorry, please continue.

[Sz]

If T(n) = 4n² + n, you can effectively say

T(n) = O(n²), because 5n² (or 6n²... or whatever) dominates 4n² + n. The Big-O of a function is the upper bound, remember, so we could say it's O(n³), but that wouldn't be very useful -- it doesn't tell us much about the function. You want the smallest possible upper bound you can find, generally.
T(n) = Ώ(n²), because 4n² (or 3n² ... or 2n² ... or n²) is a lower bound with the same asymptotic behavior. Like Big-O, you want the tightest possible bound -- in this case, the largest lower bound, you can find.

So:
T(n) = ϴ(n²) -- the largest term dominates the behavior as you approach infinity, which is (I may have neglected to say) what we're really interested in when we want the Big-Theta or Big-O of a function. All that means is that you can essentially drop out everything but the largest term. If T(n) = 4n² + 3000n + nlogn + sqrt(n), you still will end up with ϴ(n²).

I guess we could say:
T(n) = O(5n²)
T(n) = Ώ(4n²)
T(n) = ϴ(4n²)
...if specifics are necessary.


I provided that example because, rather than an elementary excersize in the notation, it's an example where you actually have to use Big-O and Big-Omega to find the ϴ-bound solution. It's one thing to look at T(n) = 2T( ceiling[n/2] ) + n and say "oh, that's ϴ(nlogn), because it's the same as 2T(n/2) + n", but to prove it you actually need this stuff.

For the more basic stuff we have here -- it seems pretty unnecessary.


Anyway, the basic relationship is:

Ώ() <= T(n) == ϴ() <= O()

[Seph]

kulock said:

"It's Showtime!"

Sorry, please continue.

Damn you, I was gonna do that >[

[Epon]

Danke. I rocked that part of the exam. The open ended parts where we had to do some stupid bi-directionaly bubblesort bollocks is another thing, though. :E

[Andrusi]

seph said:

kulock said:

"It's Showtime!"

Sorry, please continue.

Damn you, I was gonna do that >[

Clearly, in comparison to Kulock, you are a worthless consumer model.

[Kulock]

ANNIHILATE.

[Andrusi]

CHARGE.

[J]

Chrome Buster!

[SoNick Belmont]

FIREPOWERLASER!

[Sz]

WAY TO DUMB UP THE TOPIC GUYS

[Kulock]

EGGMAN ROBOT! YOU WILL BE ELIMINATED!