What does Big-Theta mean?

Question

I am studying complexity time and I found three natations: Big-O, Big-Omega and Big-Theta.
I understood that Big-O checks the worst case while Big-Omega checks the better case, however, and Big-Theta?
Is it used when the worst and better case are the same ir when I am checking a specific input?

Answer 1

It's not really about best- and worst-case!

Let's say you have analyzed the worst-case of your program to be around n² steps (like Bubblesort!)

Big-O now is any upper bound on that. So O(n²), O(n³), O(n!) all describe your algorithm accurately.

Big Omega is any lower bound. Bubblesort is Ω(n²), Ω(n), and Ω(1).

Big Theta specifies the exact growth. Bubblesort is Θ(n²), but none of the others.

(Usually, when a programmer says O(something), they mean Θ(something). Probably because nobody has a greek theta on their keyboard.)

You can do the same calculations for the best case of your program and also use O/Ω/Θ to describe that.

Honestly in programming I personally never need anything other than Θ. In mathematics O is probably the most common.

https://www.sololearn.com/discuss/1594019/?ref=app

Answer 2

Thank you so much ✌✌