Big Omega, Big Oh, Big theta

0
votes

I am reading a book Data Structures by Yashavnt P. Kanetkar. In page no. 11 of the book, I found out there are three categories of algorithms as stated by the book :

a. Algorithms that grows at least as fast as some function.

b. Algorithms that grow at the same rate.

c. Algorithms that grow no faster.

Later it is stated :

a. is Big Omega (n)

b. is Big theta (n)

c. is Big Oh (n).

I couldn't understand the meaning so searched for some youtube videos. What I learnt from them was Big Omega is the representation of best case scenario. Big Oh is the representation of the worst case scenario. Big theta is the representation of the average case scenario. I know what these cases are. However I can't understand what the book tried to mean by those three categories and how are they related to the three case scenarios.

1
algorithmbig-o
Big theta is not average case; big theta is when the upper and lower limits are the same. - Jiří Baum
This question has been asked and answered multiple times. See for example the related links in the right side bar. - Henry
I wouldn't call these "three categories of algorithms". Those are just three categories of statements that can be made about a given algorithm and a given function. If you're proud of your algorithm, you want to prove that your algorithm is "at least as fast as ...". Then I arrive with my algorithm, and I want to say that your algorithm was not that good, so I prove that your algorithm is "no faster than...". Then some theorist arrives and calculates the exact complexity of your algorithm, and they can say your algorithm "grows at the same rate as...". - Stef
Additionally, it's not always Ω(n), Θ(n) and O(n); it can be Ω(f(n)), Θ(f(n)) and O(f(n)) for some function f(n). - Stef

1 Answers

0
votes

Big Theta is a mathematician's approximation, answering the question "how well will it scale"; as the problem gets bigger and bigger, how much more time/memory will the function take? It strips away any constant factors and any terms that become less significant as the problem gets bigger, to leave just one simple expression.

Big Oh is a variant where you're giving "no worse than"; this is sometimes easier to work out, and it errs on the side of being conservative, so it's still useful.

Big Omega is the opposite variant where you're giving "no better than". This is also sometimes useful, but less often.