0

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?

igelr
  • 1,491
  • 2
  • 10
  • 25
  • "Big O" is an upper bound on complexity. There is no requirement that it be a *close* upper bound - that running time is also O(n^5), or O(n^100). In fact, this is also O(n^3), as demonstrated in Example 1 from the paper you linked to. – BJ Myers Feb 27 '19 at 19:03
  • Possible duplicate of [What is the difference between Θ(n) and O(n)?](https://stackoverflow.com/questions/471199/what-is-the-difference-between-%ce%98n-and-on) – BJ Myers Feb 27 '19 at 19:05

2 Answers2

1

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.

Akash Chandwani
  • 550
  • 1
  • 9
  • 20
1

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.

Jon Doe
  • 167
  • 1
  • 11