Time complexity: if/else under for loop

Question

If in a situation like the following (an if/else statement under a for loop) would the time complexity be O(n) or O(n^2):

def power_dic (n,k)
    if (k=0):
        return 1
    elif (k mod 2 = 0):
        return power(n*n, k/2)
    else
        return n*power_dic(n, k-1)

The above code computes n^k.

Answer 1

In situations like this, you need to analyze how the code behaves as a whole. How many times each of the return statements are going to be called, the relations between then and the input.

---

In this specific example:

The time complexity is O(logk) (assuming all int multiplications are O(1)).

For each time return power(n*n, k/2) is called, return n*power_dic(n, k-1) is called at most once⁽¹⁾.

In addition, return power(n*n, k/2) is called O(logk) times, since you reduce it by half each time it is called.

This means, your total complexity is 2*logn, which is O(logk).

---

(1) Except maybe the last bit, where you call power_dic(n,1), but that one time does not change the answer.