0
$\begingroup$

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?

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

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.

$\endgroup$
0
$\begingroup$

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)$.
$\endgroup$
  • 1
    $\begingroup$ If range n generates the whole set $\{0, \dots, n\}$ before running the loop, then constructing that set will take linear time. $\endgroup$ – David Richerby Oct 7 '18 at 20:14
  • $\begingroup$ Actually, range(n) should generate the set $0,\ldots,n-1$. $\endgroup$ – Yuval Filmus Oct 7 '18 at 20:17
  • $\begingroup$ @YuvalFilmus depend on the python version stackoverflow.com/questions/30081275/… $\endgroup$ – kelalaka Oct 7 '18 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.