1
$\begingroup$

I am confused about calculating the time complexity of the following function.

def contains(lst, delta) : 
  j = 0
  for i in range(0, len(lst)):
    while (j < len(lst)-1) and (lst[i]-lst[j] > delta):
      j = j + 1
    if lst[i]-lst[j] == delta:
      return True
return False

The function looks for 2 elements in a list for which their difference equals delta. My confusion lies in the answer: I defined n = len(lst). After working out the individual time complexities I multiplied the time complexities of the while and for loop because both were dependent on n. When I looked at the answer sheet they stated that the while loop could only be executed n times and this number was independent of the for loop, and thus their time complexities had to be additioned and not multiplied.

Could someone explain to me why this is the case and the general reasoning required for such cases?

Thanks for your time!!

$\endgroup$

3 Answers 3

-2
$\begingroup$

Big-O is about worst-case, this means you can typically focus on a simplified version of the function you've got.

For worst-case, you need the consider the case where the early returns is not taken, so remove it:

def contains(lst, delta): 
    j = 0

    for i in range(0, len(lst)):
        while (j < len(lst)-1) and (lst[i]-lst[j] > delta):
            j = j + 1

    return False

And in the absence of early return, then the second part of the while condition is useless:

def contains(lst, delta): 
    j = 0

    for i in range(0, len(lst)):
        while (j < len(lst)-1):
            j = j + 1

    return False

And finally, note that i doesn't appear in the while loop any longer, and j is not reset within the for loop, so the two loops are now independent:

def contains(lst, delta): 
    j = 0

    for i in range(0, len(lst)):
        pass

    while (j < len(lst)-1):
        j = j + 1

    return False

And now, the complexity should be simpler:

  • The for loop is executed len(lst) times.
  • The while loop is executed len(lst) - 1 times.

Thus the complexity is 2 * len(lst), aka O(len(lst)).

$\endgroup$
2
$\begingroup$

Here's the gist of it, but you should try to make it more formal on your own.

Ignore, for now the "if bla bla, return True" part.

Notice that essentially any time anything interesting happens, either i or j gets incremented, and they never decrease. They will only keep getting incremented until they reach n. Hence at most $O(n)$ "interesting" operations.

If, on the other hand, we reset j to 0 in each (or in sufficiently many) iterations of the for loop, then you would need to think like you did originally.

$\endgroup$
1
  • $\begingroup$ If I understand it correctly, because j does not get reset the while does not restart and can eventually only reach a maximum of n iterations, the for loop can also reach a maximum of n iterations and thus we sum the time complexities. In contrast, if j does get reset to 0 the while loop would have to restart n times and because the for loop iterates n times this results in O(n^2) $\endgroup$
    – Skaeler
    Commented May 28 at 22:09
0
$\begingroup$

There is no simple rule with O(f(n)). If loop 1 takes $\Theta(f(n))$ and loop 2 which is run once for every iteration of loop 1 takes $\Theta(g(n))$, then the total is $\Theta(f(n) \cdot g(n))$. The same is true for Big-O, but if you know that something is say $O(n^3)$ then there is often the possibility that it is $O(g(n))$ for some significantly smaller function g(n).

That's especially true if the inner loop can exit early, and the outer loop is designed to create conditions so that the inner loop often exits early. Or you might have a case where each iteration of the inner loop has a high maximum of iterations, but the total iterations in n executions are much less than n times as much. Say the inner loop increases a counter by one on each iteration, and exits if the counter reaches $n^{1.5}$. The inner loop runs n times and for other reasons each run can do n iterations. Now the total number of iterations is limited to $n^{1.5}$ and not to $n^2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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