Complexity Maniac

Computer Science Level pending

Agnishom gave Chris a program written in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def comp(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    val = 0
    for i in range(a):
        val += comp(n-1)
    for i in range(b):
        val += comp(n-2)
    return val

How many ordered pair of non-negative integers \((a,b)\) are there such that the time complexity of this recursive function is \(O(3^n)\)?

×

Problem Loading...

Note Loading...

Set Loading...