Algorithm Analysis Big O notation

Question

def function(n):
    if n <= 1:
       return
    function(n / 2)
    function(n / 2)

I just wonder why this function have a O(n) runtime.

I see that every time this function get call it gonna reduce the size of the input by 2. So I think the runtime gonna be nlog(n) because it have call the function 2 time so it is n and it call it self but reduce the input by 2 so I think that is another logn.

Answer 1

Here is a simplified analysis ignoring the constant work done in the function (which isn't correct as pointed out in the comment, but will help understanding the steps). Since the function is calling itself on halved input twice, we can write the running time as

T(n) = 2 * T(n/2)

Expanding it further:

T(n) = 2 * T(n/2) = 4 * T(n/4) = ... = K * T(n/K) = n * T(1)

( We see it is getting the form of K * T(n/K). The last element is K*T(1), and since we have shown that 1 = n/K, then K of the last element equals n )

Since K(1) is O(1), then the n*K(1) is O(n).

---

Now if we do consider the constant work in each call, we should rewrite it as following:

T(n) = 2 * T(n/2) + C

Now expand:

T(n) = 2 * T(n/2) + C = 
= 2 * (2 * T(n/4) + C ) + C = 4 * T(n/4) + (2 + 1)*C =
= 4 * (2 * T(n/8) + C ) + C = 8 * T(n/8) + (4 + 1)*C =
...
= K * T(n/K) + (K/2 + 1) * C

Again, for the last element K = n, so T(n) = n * T(1) + (n/2 + 1) * C

Both n * T(1) and (n/2 + 1) * C parts of the sum are O(n), so overall complexity is O(n).