1
$\begingroup$

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)

$\endgroup$

2 Answers 2

1
$\begingroup$

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)$

$\endgroup$
0
$\begingroup$
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).

$\endgroup$
1
  • $\begingroup$ In the future, answers are more helpful when they include reasons. Welcome to the site! $\endgroup$ Apr 22, 2019 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.