CODEWITHSUNDEEP
algorithmbig-o
Sharat Chandra
Sharat Chandra

Reputation: 4544

Confused on whether to express time complexity with theta notation or Big Oh notation

How to decide on expressing time complexity of algorithm ?

Should we choose to express time complexity in terms of O(n) or theta(n) ? Because a function f(n) can be expressed as either Big-Oh(g(n)) or theta (g(n)).

When do we choose big-oh over theta ?

Upvotes: 2

Views: 1067

Answers (1)

Wayne
Wayne

Reputation: 60414

Use Big Theta notation when you want to also specify a lower bound. f(n) = O(g(n)) says that f is bounded above by g, whereas f(n) = Theta(g(n)) says that f is bounded both above and below by g.

In other words, there are constants k1 and k2 such that k1 * |g(n)| <= |f(n)| <= k2 * |g(n)|

Upvotes: 5

Related Questions