The difference between Big-oh and theta notation

[arh]

Hi guys. Gotta a CS exam coming up this sunday and I want to clarify the difference between bigO and theta notation. I know that bigO is the upperbound and it has a constant after which all running time will be below. I know that theta has an upper and lower bound for this running time, but I'm still a bit confused. Here are some questions:

1) Do big-oh and theta both represent the worstcase for the running time?
2) How do I know when to use theta? I know it is better to use but how do I know when I can use it? Could someone give a simple example of when to use theta?

thanks in advanced,

arh

[Narue]

>1) Do big-oh and theta both represent the worstcase for the running time?
They represent whatever case you're analyzing.

>2) How do I know when to use theta?
Theta is when you can achieve it. It's a much stronger claim than Big O because it's a tighter bound.

[arh]

Thanks for the reply. I was able to figure it out by reading some other stuff online.

[Eko]

For those who want to understand the asymptotic notation, try this link:http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/LectureNotes/index.htm

It's a very good site with video lectures from m.i.t.(the asymptotic notation is in the second lecture)

Good luck