The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
87 views

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.4k points) | 87 views
+1
Answer is option B.

RR for fun1

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

RR for fun 2

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

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.

+2

@rishav

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:

y=fun(n-1)

z=2*y

return z

+1

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 (879 points)

Related questions

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,092 questions
55,276 answers
190,803 comments
86,086 users