Time Complexities That Are Tricky to Prove

for (int i=2; i<=e; i++)
    for (int j=i; j<=e; j+=i)

Loop i from 2 to e, and for each i, start j at i and keep adding i until e.
You can think of it as running e/i times for each i.
(e is an arbitrary positive integer, not 2.71)

Written as a formula:

\sum _{i\ =\ 2}^e\frac{e}{i}\ =\ e\sum _{i=2}^e\frac{1}{i}

It becomes the harmonic series multiplied by e.
Now, for a monotonically increasing function, the following holds.

\int _{n-1}^mf\left(x\right)dx\le \sum _{i=n}^mf\left(x\right)\le \int _n^{m+1}f\left(x\right)dx

Let f(x) = 1/x; since f(x) = 1/x is a monotonically increasing function,
let's substitute it in and find the time complexity. (substitute f(x) = 1/x, n = 2, m = e)

Lower bound :

e\int _1^e\frac{1}{x}dx\ =\ e\left(\log e\ -\ \log 1\right)\ =\ e\log e\ =\ \Omega \left(e\log e\right)

Upper bound :

e\int _2^{e+1}\frac{1}{x}dx\ =\ e\left(\log \left(e+1\right)\ -\ \log 2\right)\ =\ O\left(e\log e\right)

We usually care about the upper bound, so we can conclude the following.

O\left(e\log e\right)

Comments