Time complexity with an "or" in return statement

user_9487216 0
Viewed 410

I have the following code and want to calculate the time complexity:

def solve(n):
    if n == 0 or n == 2:
        return True
    elif n == 1:
        return False
    else:
        return not solve(n-1) or not solve(n-2) or not solve(n-3)

If I had something like this:

return solve(n-1) + solve(n-2)

it would be T(n) = 2T(n-1), at least from my understanding.

But how do I proceed if I have an "or" in the return statement?

return not solve(n-1) or not solve(n-2) or not solve(n-3)
recursion complexity-theory time-complexity time python
4 Answers

Short circuiting is the key concept in that case:

return not solve(n-1) or not solve(n-2) or not solve(n-3)

If the first function's result is false, thus the first operand of the logical ORs is true, then the other functions do not need to be evaluated (we already know the overall result).

If the first function's result is true, then we need to evaluate the second function. Following the same way of thinking as above, if that second operand evaluates to true, then we are done, and we don't need to call the third function.

If both the first two functions's results are true, then we need to evaluate the third function as well, to evaluate the expression in overall.

And since we talk about time complexity, you need to think in terms of worst and best case scenario.

  • Best case: One function call. Time complexity: T(n - 1).
  • Worst case: Three function calls. Time complexity: T(n - 1) + T(n - 2) + T(n - 3).
user_24113200

You should consider the worst case. Let's assume that not solve(n-1) and not solve(n-2) return False. In this case, solve(n-3) will be always evaluated.

In terms of complexity, it's the same as calculating:

solve(n-1) + solve(n-2) + solve(n-3)
user_17354060

Usually, when talking about time complexity, we think in terms of worst-case scenario. Here, in the absolute worst case, you will compute solve for the case n-1, n-2, and n-3.

Therefore, T(n) = T(n-1) + T(n-2) + T(n-3)

user_81474550

The worst time complexity of return not solve(n-1) or not solve(n-2) or not solve(n-3) is T(n-1) + T(n-2) + T(n-3).

And the best is T(n-1).

Because a or b does not evaluate b if a is True.

user_47362440
Related