CODEWITHSUNDEEP
time-complexitybig-o
user3469277
user3469277

Reputation: 1

complexity for recursive functions (Big O notation)

I have two functions which I would like to determine the complexity for.

The first one I just need to know whether my solving is correct, the second one because of the two recursive calls I am struggling to find the solution to, if possible would be good to have the working out so that I can learn how its done.

First:

def sum(list):
    assert len(list)>0
    if len(list) == 1:
        return list[0]
    else:
        return sum(list[0:-1]) + list[-1]

Attempted solution : 

T(0) = 4
T(n) = T(n-1) + 1 + c -- True for all n >0 

T(n) = T(n-1) + 1 + c
     = T(n-2) + 2 + 2C
     = T(n-k) + k = kC --(n-k = 0 implies that k=n)
T(n) = T(0) + n + nC
     = T(0) + 2nC --(T0 is nothing but 4)
     = 6nC
Complexity = O(n)

Second:

def binSum(list):
    if len(list) == 1:  
        return list[0]
    else:
        return binSum(list[:len(list)//2]) + binSum(list[len(list)//2:])

Any help would be greatly appreciated.

Regards

Upvotes: 0

Views: 1059

Answers (1)

blazs
blazs

Reputation: 4845

For the first case, you can model the time complexity with the recursive function T(n) = T(n-1) + O(1) and T(0) = O(1). which obviously solves to T(n) = O(n).

Here's a more direct and more formal proof by induction. The base case is easy: T(0)<=C by the definition of O(1). For the inductive step, suppose that T(k) <= C*k for all k<=n for some absolute constant C>0. Now T(n+1) <= D + T(n) <= D + C*n <= max(C,D)*(n+1) by the inductive hypothesis, where D>0 is an absolute constant.

For the second case, you can model the time complexity with T(n) = T(n/2) + T(n/2) = 2T(n/2) for n>1 and T(1)=O(1). This solves to T(n)=O(n) by the master theorem.

Upvotes: 0

Related Questions