CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
CrackerBarrelKid55
CrackerBarrelKid55

Reputation: 608

Representing an algorithm of different O and Omega complexities with Big Theta notation

From what I've seen, Big Theta can only be used for an algorithm of the same O and Omega complexities. However I've been told that an algorithm can still be represented using Big Theta notation, regardless of the O and Omega complexities. I'm unsure how this can be the case as it seems to go against the definition of Big Theta. Thanks!

Upvotes: 1

Views: 523

Answers (1)

Patrick87
Patrick87

Reputation: 28312

f is Big-Theta of g if and only if f is both Big-Oh and Big-Omega of g. If somebody told you otherwise, they were mistaken. Now, if f is Big-Omega of g and Big-Oh of h and g grows more slowly than h, then maybe there are toghter bounds that could admit a Theta bound, but you'd need to see.

Upvotes: 1

Related Questions