after reading many articles or answers I still can't solve a problem of determining the asymptotic time complexity o a function. The function is for example like this:
def function(n):
for i in range(n):
if i == 0:
for j in range(n):
for k in range(10000):
print("output")
What will be the asymptotic time complexity due to n and how many times will be written "output" due to n?
Thank you.
In this example, the time complexity should be O(n) even though there are 3 nested loops.
The i loop runs n times.
The j loop runs n times, but only if i is 0.
The k loop runs 10000 times, but it is a constant factor.
To better explain what happens, let's distinguish between n_i, n_j even though they're both equal to n. The complexity is :
O(1 * n_j * 10000 + n_i * 1) = O(10000 * n_j + n_i) = O(n_j + n_i) = O(n + n) = O(n)
Output should be printed 10000 * n times.
If you replace the print call by a counter increment:
def function(n):
count = 0
for i in range(n):
if i == 0:
for j in range(n):
for k in range(10000):
count += 1
you can call %timeit in IPython with increasing values of n:
%timeit function(10)
5.01 ms ± 36 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit function(100)
50.4 ms ± 334 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit function(1000)
497 ms ± 1.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit function(10000)
5.03 s ± 27.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Times seem to match O(n) perfectly!
The complexity would be O(n**2) without the if:
def function(n):
for i in range(n):
for j in range(n):
for k in range(10000):
print("output")
The complexity would be O(n**3) if k is in range(n):
def function(n):
for i in range(n):
for j in range(n):
for k in range(n):
print("output")
