Skip to main content
Minor clarification.
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

You need to focus on how many times the instructions on the innermost loop will get executed. The outer loops are more like counters.

The inner-loop count will be as follows:

$i = 0; j = \emptyset$
$i = 1; j = 0$
$i = 2; j = 0, 1$
$i = 3; j = 0, 1, 2$
$\dots$

So you have a recurring sum of 1 for $j$ from $1$$0$ to $i$$i-1$, which can be mathematically expressed as:

$$\sum^n_{i = 1}\sum^i_{j = 1} 1 = \sum^n_{i = 1} i = \frac{n(n + 1)}{2}$$$$\sum^n_{i = 1}\sum^{i-1}_{j = 0} 1 = \sum^n_{i = 1} i = \frac{n(n + 1)}{2}$$
which is still $O(n^2)$.

You need to focus on how many times the instructions on the innermost loop will get executed. The outer loops are more like counters.

The inner-loop count will be as follows:

$i = 0; j = \emptyset$
$i = 1; j = 0$
$i = 2; j = 0, 1$
$i = 3; j = 0, 1, 2$
$\dots$

So you have a recurring sum from $1$ to $i$, which can be mathematically expressed as:

$$\sum^n_{i = 1}\sum^i_{j = 1} 1 = \sum^n_{i = 1} i = \frac{n(n + 1)}{2}$$
which is still $O(n^2)$.

You need to focus on how many times the instructions on the innermost loop will get executed. The outer loops are more like counters.

The inner-loop count will be as follows:

$i = 0; j = \emptyset$
$i = 1; j = 0$
$i = 2; j = 0, 1$
$i = 3; j = 0, 1, 2$
$\dots$

So you have a recurring sum of 1 for $j$ from $0$ to $i-1$, which can be mathematically expressed as:

$$\sum^n_{i = 1}\sum^{i-1}_{j = 0} 1 = \sum^n_{i = 1} i = \frac{n(n + 1)}{2}$$
which is still $O(n^2)$.

Source Link

You need to focus on how many times the instructions on the innermost loop will get executed. The outer loops are more like counters.

The inner-loop count will be as follows:

$i = 0; j = \emptyset$
$i = 1; j = 0$
$i = 2; j = 0, 1$
$i = 3; j = 0, 1, 2$
$\dots$

So you have a recurring sum from $1$ to $i$, which can be mathematically expressed as:

$$\sum^n_{i = 1}\sum^i_{j = 1} 1 = \sum^n_{i = 1} i = \frac{n(n + 1)}{2}$$
which is still $O(n^2)$.