The Gateway to Computer Science Excellence
+1 vote

Consider the following two functions. What are time complexities of the functions?

int fun1(int n)


    if (n <= 1) return n;

    return 2*fun1(n-1);


int fun2(int n)


    if (n <= 1) return n;

    return fun2(n-1) + fun2(n-1);



(A) O(2^n) for both fun1() and fun2()
(B) O(n) for fun1() and O(2^n) for fun2()
(C) O(2^n) for fun1() and O(n) for fun2()
(D) O(n) for both fun1() and fun2()

in Algorithms by Loyal (5.7k points) | 105 views
Answer is option B.

RR for fun1

T(n) = T(n-1) +1

RR for fun 2

T(n) = 2× T(n-1) +1

what i am not getting is that In fun1() return 2*fun(n-1); can be written as return fun(n-1) + fun(n-1);

then T(n)=2*T(n-1)+1 for fun1 also.



thats wrong interpretation

fun(n-1) is only called once not twice ,the constant 2 is multiplied to this function call, if you need to analyse you just need to just see how many recursive function calls there,here its 1 only


return 2*fun(n-1)

you can rewrite above statement as:



return z


thanks @Shubham Shukla


1 Answer

0 votes

BIG NOTE: 2*f(n-1)  is not equal to f(n-1)+f(n-1) because there are only one recursive call in 2*f(n-1) while there are two recursive call in f(n-1)+ f(n-1).

1. Recurrence relation for T(n) = T(n-1) + C

Solution for first code

2. T(n) = 2T(n-1) + C 

This will be O($2^{n}$ )

by Junior (905 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,688 answers
107,246 users