Time complexity with an "or" in return statement

Question

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)

Not a trivial task. See https://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm#2709195 — David Lemon, Dec 18 '18 at 12:53

gsamaras · Accepted Answer · 2018-12-18T12:51:38.780

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).

@momos I am not sure what you mean. If you need some further info that what my answer already provides, please read [Time complexity of recursive function](https://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm#2709195). — gsamaras, Dec 19 '18 at 19:20

score 1 · Answer 2 · edited Dec 18 '18 at 12:51

1

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)

edited Dec 18 '18 at 12:51

gsamaras

71,951
46
188
305

answered Dec 18 '18 at 12:40

Maroun

94,125
30
188
241

score 0 · Answer 3 · edited Dec 18 '18 at 12:41

0

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)

edited Dec 18 '18 at 12:41

Maroun

94,125
30
188
241

answered Dec 18 '18 at 12:38

Xatyrian

1,364
8
26

1

@gsamaras fixed :p – Xatyrian Dec 18 '18 at 12:41

Xiwei Wang · Answer 4 · 2018-12-18T12:51:51.753

0

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.

edited Dec 18 '18 at 12:51

answered Dec 18 '18 at 12:40

Xiwei Wang

346
4
17

This is not the reason. The reason is that `and` and `or` are shot-circuited. `a or b` does not evaluate `b` if `a` is `True`, `a and b` does not evaluate `b` if `a` is `False`. – DeepSpace Dec 18 '18 at 12:42

Time complexity with an "or" in return statement

4 Answers4