Is the time complexity of nested for, while, and if statements the same? Suppose `a`

is given as an array of length `n`

.

```
for _ in range(len(a)):
for _ in range(len(a)):
do_something
```

The for statement above will be O(n²).

```
i = 0
while i < len(a) * len(a):
do_something
i += 1
```

At first glance, the above loop can be thought of as O(n), but in the end I think that it is also O(n²).

Am I right?

·
Santiago Trujillo

Am I right?

Yes!

The double loop:

```
for _ in range(len(a)):
for _ in range(len(a)):
do_something
```

has a time complexity of O(n) * O(n) = O(n²) because each loop runs until `n`

.

The single loop:

```
i = 0
while i < len(a) * len(a):
do_something
i += 1
```

has a time complexity of O(n * n) = O(n²), because the loop runs until `i = n * n = n²`

.

·
Santiago Trujillo
Report

It is indeed still O(n^2). That is especially clear when you look at the loop which has len(a)*len(a) iterations.

You "flattened" the loops, but didn't change the amount of work, therefore it's just a "stylistic" change and has no impact on complexity.

·
Santiago Trujillo
Report

We need to determine time complexity based on the number of operations being carried out by the constructs IMHO. It wouldn't be correct to generalize and say certain loops have a particular time complexity.

The time complexity of nested for loops *generally* would be O(n squared) - not always. Some involved nested for loops can also have just O(n) complexity.
a single if statement would generally be O(1) since you are only doing basic comparisons. while loop could be anything depending on your exit condition.

while it could be useful to keep generalizations such as these in mind, we should always check the number of operations carried out to determine complexity.

·
Santiago Trujillo
Report

Let me complement the other answers.

Does time complexity change when two nested loops are re-written into a single loop?

If they do the same work, complexity does not change. :-) If it does, then (at least) one of them is doing unnecessary work.

I apologize if going too far, but let me guess: Your thinking was:

- nested loops --> multiply, i.e. "n * n" (or "n * m"), where "n" is "the usual".
- single loop --> use "n" as-is, where "n" is "the usual". I am guessing in most exercises you have seen "n" for "size".

If that is your thinking, it just needs one adjustment: for the single loop, if "n" is the length *of the loop*, note that n = len(a) * len(a); if you change the meaning of "n" from one problem to the other you cannot compare (for the nested loops, n = len(a)). In any case, both codes have O(len(a) * len(a)) complexity, which is what you already found.

·
Santiago Trujillo
Report

Time Complexity denotes the Approx. upper bound time for any Program. Let calculate mathematically Time Complexity for both and check.

For For Loop:

```
for _ in range(len(a)):
for _ in range(len(a)):
do_something
```

The outer for loop is running O(len(a)) times and inner for loop is running O(len(a)).Which is running independently of outer for loop for O(len(a)) time.

take n=len(a)

We can derive the below Function:

```
F(n) = 1*n +2*n +3*n +4*n +..........+(n-1)*n+n*n (if n starts from 1)
F(n) = n(1+2++3+4+....+(n-1)+n)
F(n) = n*(n+(n+1)/2) (Sum of n Natural Numbers)
F(n) = n^2 + 2*n + n/2 (After Solving the Equation)
F(n) = O(n^2)
```

For While loop

```
i = 0
while i < len(a) * len(a):
do_something
i += 1
```

We can directly derive that since it will run in:

```
len(a)*len(a) = n*n=O(n^2)
```

We can say that Both has approximately equal run time hence Complexity remains the same.

·
Santiago Trujillo
Report