Fûñky!

Computer Science Level pending

Consider the following python code:

from math import *


def funky( A ):
    """Takes an array A,does something funky, and
    returns a real number"""
    size = len(A)
    answer = 0
    if size <= 4:
        for i in A:
            answer -= i
        return answer
    else:
        a = funky( A[ 0 : size / 2 ]    )  
        b =  funky( A[ size - int(sqrt(size)) : size ] )
        for i in A:
            answer += log( abs( i ) + 1 , 2 )
        return answer  + a + b

Which of the following is the run time of funky(A) ? Where $n$ is the size of the input array $A$ .

\Theta(\log_3(n))

\Theta(\lg(n))

\Theta(n)

\Theta(n^2\lg(n))

1 solution

Abhishek Sinha
Mar 21, 2016

Let $f(n)$ be the run-time of the program. Then it is clear that for large enough $n$ $f(n)=f(n/2)+ f(\sqrt{n})+n$ It is clear that $f(n)\geq n$ . Now we will show by induction that $f(n)\leq 6n$ . The base case is easy. Assume that $f(n)\leq 6n$ for all $n\leq m-1$ . Now we have $f(m) = f(m/2)+f(\sqrt{m})+m \stackrel{(a)}{=}\leq 6m/2+6 \sqrt{m} + m$ where $(a)$ follows from our induction hypothesis. Assume $m \geq 9$ , then we can bound $\sqrt{m} \leq m/3$ . Hence from the above we get $f(m) \leq 3m + 2m+m = 6m$ Which completes the inductive step. Hence, we have for all large enough $n$ $n\leq f(n) \leq 6n$ Thus $f(n)=\Theta(n)$ .

Fûñky!

1 solution

0 pending reports