CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
igelr
igelr

Reputation: 1751

How to understand Big O notation in a given example

enter image description here

Here it states that T(n) is O(n^4). But I want to know why it is not O(n^3)? It contains n^3 and if we omit 20n and 1 it should be O(n^3) not O(n^4). Why it is like this?

Upvotes: 0

Views: 320

Answers (2)

Jon Doe
Jon Doe

Reputation: 167

It is in O(n^3), but O(n^4), O(n^5) etc is a superset of O(n^3), so if something is in O(n^3) then it can also be in O(n^100). The best answer and the one used by convention is the smallest big O to which is belongs, which is O(n^3), but it's not the only one.

Upvotes: 1

Akash Chandwani
Akash Chandwani

Reputation: 550

I think you are getting confused between the theta notation and the big O notation.

Theta notation determines the rough estimate of the running time of an algorithm, whereas Big O notation determines the worst case running time of an algorithm.

The method you mentioned above is used to calculate the theta, not big O. The big O of the above-mentioned problem could be O(n^4), O(n^5), O(n^6) and so on... all are correct values. But for theta, only theta(n^3) is correct.

Upvotes: 1

Related Questions