Complexity Maniac

Computer Science Level 4

Agnishom gave Chris a program written in Python.

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)$ ?

The answer is 4.

1 solution

Joe Mansley
Aug 3, 2016

${ 3 }^{ n }\quad=\quad a\cdot { 3 }^{ n-1 }+b\cdot { 3 }^{ n-2 }$

$9\quad =\quad 3a+b$ b must be a multiple of 3, so let's say $b=3{ b }_{ 2 }$

so we now have ${ b }_{ 2 }+a=3$

the solutions of which are $(0,3)\quad (1,2)\quad (2,1)\quad (3,0)$

So we have 4 solutions

Complexity Maniac

The answer is 4.

1 solution

0 pending reports