1
$\begingroup$

I am learning data structures and algorithms currently, and want to understand how the following codes received their O-notations.

Code example #1:

for (int i = N; i > 1; i--) {
  for (int j = 0; j < i; j++) {
    for (int k = 1; k < N; k = k*2) {
        doSomething(i, j, k);
    }
  }
}

The O-notation for how many times doSomething(i, j, k); is executed is: $$\theta(N^2logN)$$

Code example #2:

for (int i = N; i > 1; i = i/2) {
  for (int j = 0; j < i; j++) {
    for (int k = N; k < N+N; k++) {
        doSomething(i, j, k);
    }
  }
}

The O-notation for how many times doSomething(i, j, k); is executed is: $$\theta(N^2)$$

Code example #3:

for (int i = N; i > 1; i = i/2) {
  for (int j = 0; j < i; j++) {
    for (int k = N; k < N+N; k = k + N/10 + 1) {
        doSomething(i, j, k);
    }
  }
}

The O-notation for how many times doSomething(i, j, k); is executed is: $$\theta(N)$$

My question(s):

How do you really derive to these O expressions or time complexities, I am looking at various of mathematical methods but I won't get smarter as a result of that. I looked at few YouTube videos, but even those don't explain the basic tools and fundamentals that give you the edge in doing these calculations and steps manually on any type of code.

Why do these algorithms or for-loops for how many times the method doSomething(i, j, k); is executed derive to these O-expressions?

$\endgroup$

1 Answer 1

3
$\begingroup$

You must proceed from inner to outer.

Evaluate the number of calls to doSomething in the innermost loop.

  • #1: $\log N$, because you can double $k$ a number of times $\log_2(N)$ before you reach $N$.

  • #2: $N$ times, obviously.

  • #3: at most $10$ times, as this will add more than $N$ to $k$.

Using this information, you can evaluate for the intermediate loop.

  • For all three cases, this is just $i$ times the count for the inner loop.

Now for the external loop.

  • #1: sum of $i\log N$ for $i$ decreasing by unit steps; in total $(N+(N-1)+(N-2)+\cdots1)\log N=\dfrac{N(N+1)}2\log N$.

  • #2: sum of $N$ for $i$ following a decreasing geometric progression; in total $N\left(N+\frac N2+\frac N4+\cdots1\right)\approx 2N^2$.

  • #3: same as #2 with 10 instead of the first $N$.

$\endgroup$
3
  • $\begingroup$ Hi Yves, thanks for this. Can you possibly, disassemble one of the code examples above, and show how to do this step-wise analytically, derive to the O complexity? $\endgroup$
    – Albin M
    Apr 6, 2022 at 8:12
  • $\begingroup$ @AlbinM: I did decompose step-wise and give all the complexities, pay attention. $\endgroup$
    – user16034
    Apr 6, 2022 at 9:07
  • $\begingroup$ Yves, I know. But, I want to understand this step-wise. $\endgroup$
    – Albin M
    Apr 6, 2022 at 9:50

Your Answer

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

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