What is the upper found or Big O notation for the given functions
5^n
and 1.1^n
are exponential (growing) functions. They grow asymptotically faster than any polynomial function, which n^3
and n^2
are. (This can be proven e.g. via l'Hôpital.)
Therefore the functions are Theta(5^n)
and Theta(1.1^n)
respectively. Note that these classes are not the same, since an exponential function with a larger base/rate asymptotically dominates one with a smaller base/rate.
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
So as you can see, so the first function behave asymptotically like 5^n
, since the lower order terms when n tends to infinity are negligible. And the second one is dominated by 1.1^n
since is an exponential function and 1.1 > 1
.