CODEWITHSUNDEEP
mathcomplexity-theoryasymptotic-complexitybig-o
user2781902
user2781902

Reputation: 63

Determine the asymptotic complexity

If I'm given two functions and asked to find asymptotic complexity for both, what does that mean? Is it O() or Big Theta? For example f1(n)=a^n and f2(n)=n^3+n^2

Should I say that f1 is O(a^n) and f2 is O(n^3) or should I use big-theta?

Upvotes: 2

Views: 1165

Answers (2)

templatetypedef
templatetypedef

Reputation: 372784

O notation provides an asymptotic upper bound; if f(n) = O(g(n)), it intuitively means that f grows no faster than g.

Θ notation, on the other hand, specifies a tight bound. If f(n) = Θ(g(n)), it means f and g grow at the same rate, up to some constant factor. Technically speaking, f(n) = Θ(n) implies that f(n) = O(g(n)), though the reverse isn't always true.

The most precise analysis you can give would be to use Θ notation, though it would not be wrong to use O notation.

Hope this helps!

Upvotes: 2

jrhea
jrhea

Reputation: 61

Big Oh and Big Theta are both used in asymptotic analysis. To say that a function f(n) = O(n^3) means that it grows no faster than n^3. To say that a function f(n) = Θ(n^3) means that it grows as fast as n^3.

Upvotes: 1

Related Questions