# Help with Time Complexity

Suppose we have the function below:

def func(n):
for i in range(n):
for j in range(n - i):
for k in range(n - j):
if i + j + k == 0:
break
if i + j == 0:
break
if i == 0:
break
return n + 1


We have three nested for-loops and the total number of elements evaluated appears to be: (n)(n-1)(n-2). However, this cannot be correct, as I know the time complexity of this function is not O(n^3). What is the proper way to evaluate the time complexity of this function?

• Could you please rewrite your code as pseudocode so people don't have to understand what the range command does in Python? – David Richerby Oct 7 '18 at 20:14
• also, put eval() function to where it is supposed to be. – kelalaka Oct 7 '18 at 20:42

Your function has constant running time (or linear running time, depending on how range is implemented). I suggest running it step-by-step and seeing what happens.

If this is for Python 3.0 then by this knowledge;

• Your function is constant time $$\mathcal{O}(1)$$. Since every loop runs once end finishes.

If Python version < 3.0;

def func(n):
for i in range(n):             #generates all the numbers at once
for j in range(n - i):     #generates all the numbers at once
for k in range(n - j): #generates all the numbers at once
if i + j + k == 0:
break
else:
eval()
if i + j == 0:
break
if i == 0:
break
return n + 1

• Since each loop actually runs once the result will be $$\mathcal{O}(n)$$ assuming that your eval function is in $$\mathcal{O}(n)$$.
• If range n generates the whole set $\{0, \dots, n\}$ before running the loop, then constructing that set will take linear time. – David Richerby Oct 7 '18 at 20:14
• Actually, range(n) should generate the set $0,\ldots,n-1$. – Yuval Filmus Oct 7 '18 at 20:17
• @YuvalFilmus depend on the python version stackoverflow.com/questions/30081275/… – kelalaka Oct 7 '18 at 20:29