If someone could help me with:
1- what is the time complexity (Big O) of this code?
2- if the big O of this code = O(n^2) then which is better to use (while like this code) or (two nested for loop)?
the code:
l = [1, 2, 3, 4, 6, 5] // big O => O(1)
ll = list(l) // big O => O(1)
a = 0 // big O => O(1)
b = 1 // big O => O(1)
x = 0 // big O => O(1)
y = 0 // big O => O(1)
while a < len(l)-1: // big O => O(?)
x = l[a] // big O => O(1)
y = l[b] // big O => O(1)
if x > y : // big O => O(1)
ll[a] = 0 // big O => O(1)
a += 1 // big O => O(1)
b =a+1 // big O => O(1)
elif b >= len(l)-1: //big O => O(1)
a += 1 // big O => O(1)
b = a + 1 // big O => O(1)
continue // big O => O(?)
else : // big O => O(1)
b += 1 // big O => O(1)
continue // big O => O(?)
print(ll) // big O => O(1)
In the worst case of above code make while loop executed sum of (n-1) time for example:
if n = 1 then while loop will execute 0 time
if n = 2 then while loop will execute 1 time
if n = 3 then while loop will execute 3 time
if n = 4 then while loop will execute 6 time
if n = 6 then while loop will execute 15 time
.
.
.
if n = k then while loop will execute sum(k-1) time
I hope my question is clear.
The time complexity of your code is O(𝑛²).
Some remarks on your analysis:
ll = list(l) // big O => O(1)
The list function (in Python) creates a new list, so this is actually O(𝑛)
continue // big O => O(?)
The continue statement takes constant time to execute, so O(1). However, where you use continue, you can simply delete those statements, as they have no effect (they are already the last statement executed in the current iteration of the loop).
print(ll) // big O => O(1)
Printing a list takes as much time as the list is long (every single character needs to be output), so this is O(𝑛). On the other hand, printing is not something that should be part of complexity analysis. You should better write your algorithm as a function, which just returns the result. It is up to the caller to decide whether that list should be printed or not, and anyway that is not part of the algorithm and should not be analysed.
The main question is how many times the loop makes an iteration. If we discard the if block that starts with if x > y, then a and b get values that are all the possible pairs you can take from {0,..,𝑛−1} where a < b. So for example, if 𝑛 is 4, the values for a and b evolve like this:
| iteration | a | b |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 0 | 2 |
| 3 | 0 | 3 |
| 4 | 1 | 2 |
| 5 | 1 | 3 |
| 6 | 2 | 3 |
So there are 3 iterations where a 0, 2 iterations where a is 1, and 1 iteration where a is 2. This makes a total of 1+2+3+...+𝑛−1 iterations, which is a triangular number and can be expressed as 𝑛(𝑛−1)/2, which is O(𝑛²).
O(𝑛²) is the worst case complexity, because the if x > y block may cause a to increase faster than explained above. In the best case, your input would be a decreasing sequence ([5, 4, 3, 2, 1]), and then this if block will execute in every iteration of the outer loop, so that you only get 𝑛−1 iterations of the outer loop, which makes it O(𝑛).
In Python it is considered better practice to not have explicit a += 1 statements on the loop variable, but use iterators or ranges to loop over. For instance, the same logic is implemented by this code:
def solve(l):
return [
0 if any(l[b] < x for b in range(a + 1, len(l))) else x
for a, x in enumerate(l)
]
Here any is used to find out if there is any b (after a) for which l[b] < l[a]. If so the value at a should be replaced with 0, if not, we keep the original value x. This list comprehension creates a new list, and so it combines your list(l) call with the logic in the loop.
We can also use a different algorithm that is more efficient. If we traverse the list backwards, then we can track the minimum value encountered so far. Whenever we encounter a value that is greater than that minimum, we replace it with a 0. This way we don't have an inner loop, and the process becomes O(𝑛):
def solve(l):
low = l[-1] # keep track of the least value found so far
result = [
0 if (low := min(y, low)) < y else y
for y in reversed(l)
]
result.reverse()
return result