CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Diego Vinicius
Diego Vinicius

Reputation: 182

Why is an algorithm complexity given in the Big O notation instead of Theta?

I know what the Big O, Theta and Omega notations are, but for example, if my algorithm is a for inside of a for, looping n times, my complexity would be O(n²), but why O(n²) instead of ϴ(n²)? Since the complexity IS in fact O(n²) and Ω(n²), then it would also be ϴ(n²), and I just can't see any reason to not use ϴ(n²) instead of O(n²), since ϴ(n²) restricts my complexity with an upper and bottom value, not only upper in the case of O(n²).

Upvotes: 4

Views: 67

Answers (1)

abc
abc

Reputation: 11949

If f(n) = Θ(g(n)) then f(n) = O(g(n)). This because Θ(g(n)) ⊆ O (g(n)).

In your specific case if a loop runs exactly n^2 time the time complexity is in both O(n^2) and Θ(n^2).
The main reason why big-O is typically enough is that we are more interested in the worst case time complexity when analyzing the algorithm's performance, and knowing the worst case scenario is usually enough. Also, not always is possible to find a tight bound.

Upvotes: 4

Related Questions