Recursion size

Computer Science Level 3

Consider the recursive functions below which output the same value:

def rec1(n):
    if n <=1:
        return 1
    else:
        return 2*rec1(n-1)
def rec2(n):
    if n<=1:
        return 1
    else:
        return rec2(n-1) + rec2(n-1)

What is the running time of the algorithms?

O(n)

for the first and

O(2^{n})

for the second

O(2^{n})

for the first and

O(n)

for the second

O(n)

for the first and

O(n^{2})

for the second Both in

O(2^{n})

Both in

O(n)

1 solution

A Former Brilliant Member
Dec 25, 2018

rec1 has linear descent to n=1. rec2 bifurcates at each level of descent to n=1. $(\sum _{i=0}^{n-1} 2^i)$ + 1 for the original call gives $2^n$ .

Recursion size

1 solution

0 pending reports