World's most popular travel blog for travel bloggers.

# [Answers] How to express time complexity when the exponential "e" comes into play?

, ,
Problem Detail:

I am new to all of this and I am trying to understand how to define Time Complexity. I have an algorithm which performs a set of operations on inputs of different size.

While timing the execution of such algorithm I have figured out that the time elapsed follows an exponential law:

``Time(size)=0.15*exp(0.05*size) ``

My question: is it correct to define this complexity according to

`T(n)=O(e^n)`?

#### Answered By : Tanner Swett

It depends on whether you're talking about \$O\$ or \$\Theta\$. The notation \$O\$ indicates that the complexity is "this much or smaller", and the notation \$\Theta\$ indicates that the complexity is "this much, no more or less".

The complexity of \$0.15 e^{0.05 n}\$ is \$\Theta(e^{0.05 n})\$. The complexity is not \$\Theta(e^n)\$, because \$e^n\$ grows faster than \$e^{0.05 n}\$ does (the ratio between the two increases without bound).

It is, in fact, true that \$0.15 e^{0.05 n}\$ is an \$O(e^n)\$ function, but this isn't a good description of the complexity, in much the same way that "more than a thousand people live in China" is not a good description of the population of China.

What this comes down to is that you should state the complexity as \$\Theta(e^{0.05 n})\$ or as \$O(e^{0.05 n})\$.