# What is the time complexity of it?

I can calculate the time complexity of the following loop:

for (int i = 1; i < n; i++)

The time complexity of it is $$O(n)$$.

but I can't calculate the time complexity of the next two loops.

I can't find any hints.

for (int i = 0; i < n; i+= 2)

for (int j = 1; j < n; j*= 2)

Its hard to tell what the "complexity" of a loop without knowing what each iteration performs, but what we can do is count how many times each loop iterates:

for (int i = 1; i < n; i++)

You correctly stated this loop iterates $$n$$ times.

for (int i = 0; i < n; i+= 2)

The above loop iterates until $$i \geq n$$, or in other words, $$k$$ times, when $$i+2k = n \rightarrow 0+2k = n$$ (since you initiate $$i=0$$ and increment it by $$2$$). Solve the trivial equation, and you get $$k=\frac{n}{2}$$, which is $$O(n)$$ iterations.

for (int j = 1; j < n; j*= 2)

Same as the second time, we must solve $$2^k = n$$, since you multiply $$j=1$$ by $$2$$ each iteration. Solve and get $$k=\log(n)$$

for (int i = 0; i < n; i += 2)


has the time compexity O(n) and

for (int i = 0; i < n; i *= 2)


has the time compexity O(ln n).

• In the future, answers are more helpful when they include reasons. Welcome to the site! – Rick Decker Apr 22 '19 at 17:07