GATE CSE 2016 Set 2 | Question: 39

Question

The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O(n^{\alpha})$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is ________.

Flow chart for Recursive Function $A(n)$.

Comments

thanks sir 🙂

this clears all my doubt.

---

@Sachin Mittal 1
sir can we say by  “least possible value of ‘a’, they infer tightest upper bound?

---

@Debanjan_2000 yes right

Answer 1

If they are asking for worst case complexity hence,
By calling $A(n)$ we get $A(n/2)$ $5$ times,

$A(n)=5A (n /2) + O(1)$

Hence, by applying masters theorem,
Case 1 : $a>b^k$

$n^{\log_25}$

Thus value of alpha will be $2.32$

Comments

What about 2.33 ?

---

as per virtual calci answer is 2.3219... even you round up, it will be 2.32

---

I think there will be small range like 2.31-2.33 in exam paper .

---

may be, but they said accurate upto two decimals.

---

Hmm.. Then something like 2.320-2.322 ! They always keep small range. Never seen too strict answer for float, because in that case something like 2.321 might be wrong, which is factually correct & more accurate !

---

becoz of Big Oh i thought 2.32 to be wrong..

---

also they have mentioned 'least possible value'. What does it stand for? Little confusing!

---

Lets wait for @Arjun or @Praveen to clear up confusion here !

---

Least is needed or else even 3 can be a possible answer. 2.32 is fine assuming round off. But 2.33 should be given marks as it is a better answer due to big O.

---

I answered 2.321 , will I Get 0 ?

---

Nopes. Because the answer should be evaluated using < and >

---

I'll still consider as 0, tentatively (Untill IISc says otherwise ! ) I @amar did have a solid point, but I believe that this 2 marks wont matter , because majority people would have answer 2.32 anyway

---

2.31-2.33 is my expected answer. So shouldn't be an issue :)

---

Can anyone tell me why we have 5 A(n/2)s and not 6?

---

follow the flowchart and see the worst case scenario.

The worst you can end up is 5 times recursion.

The sixth one which you are counting is the best case (only 2 splits)

---

i have one doubt here,according to ur recurrence,it is meant that at every level,n is divided into n/2 5 times,i.e first level n,then next level calling 5 times (n/2),then next level,calling n/2 5 times.

but that is not happening.

at first level,we have just 'n/2' numbers.

thn at next level,we divide it into n/4 and n/4 .then we will divide one of them into n/2 again, so,we get n/8

next according to a condition,we again divide previous level n/8 into n/16 again.then again if conditon is met,we divide this n/16 into n/32 and then stop.

please clear this doubt.here we are not dividing into 5 parts at each step.so how is it 5T(n/2)

---

no no..u r getting it wrong.

See this.

A(n)

{

A(n/2);

A(n/2);

A(n/2);

A(n/2);

A(n/2);

}

Now what do you think? It should be 5T(n/2) ir not??

---

@lucky,,is it not that n--> n/2 --> n/4 --> n/8 --> n/16 --> n/32 is happening here??

then firstly a(n/2) is called.

then after checking condition ,previous function call will call a(n/2),which is a(n/4)...

then a(n/4) will call a(n/2) i.e a(n/8) and so on..

i thought this is happening hre

---

ok..Lets see it like this:

n=32.

A(n)

{

A(n/2);// here A(16) will be called. (n=16) ,but this is a new n for A(16). It is nowhere related to n in A(32).
// here you think n becomes 16.Have we done anywhere n=n/2 NO! Without that it will not become 16.
A(n/2);

A(n/2);

A(n/2);

A(n/2);
//n is still 32.
}

please ask if yet not clear.

---

ooh..okay..i got you.i thought that it is calling recursivly one aftre another.thanks a lot for clearing this doubt.:)

and one thing more,you said that here we have not made n=n/2,i did nt get this point

while making normal recursion functions,when we write like this-

func(n)

{........

........

return (func(n/2));

}

here,also we are not make n=n/2 anywhere but still recursion goes like n -> n/2 -> n/4 -> n/8 --and so on...

---

and one more doubt,if the question would had been according to my underrstand thn T(n) would have been O(1)..right??as there would have been 5 levels and at each level,there will be constant work..which nearly becomes constant..am i correct??

---

func(n)

{........

........

return (func(n/2)); // after this line func(n/2) is called.
// but here n is still unchanged.
}

func(n/2) // here that n/2 effects.

{

...

}

---

yea..thats true..thanks:)

---

If question would have been according to your understanding:

Let for n inputs the time complexity beT(n).
So, we can write T(n)=T(n/2)+C //level 1.
Lets solve it by substitution.
 T(n)=T(n/2)+C
 T(n)=T(n/4)+2C
 T(n)=T(n/8)+3C
 T(n)=T(n/16)+4C
 T(n)=T(n/32)+5C   // now they stopped. and this is the TC O(n/32 +5).
If n would have been 32, TC would be 5, which is logn

---

@Arjun Sir, Kindly comment.

---

Fixed now. Thanks for notifying.

---

Here in the question itself mentiobing that it is recursive program...

---

This is my first Gate Attempt, so I don't have much idea. How are we supposed to find out the value of log5 accurate upto 2 decimal places in exam?

---

Use virtual calculator. you can find an app for that in Google Play

---

Do Log 5 / Log 2

https://www.youtube.com/watch?v=xU57pyzNma0

---

masters theorem give Θ()big Theta but here we need O()big O.

please clearify

 

---

What was the range of the answer then? 2.31-2.33 ?

---

In the scientific calculator when i typed log5/log2, it was showing 0.301(which is only the value of log2) because i hadn’t pressed enter button !!! this cost me 2 marks

---

masters theorem give Θ()big Theta but here we need O()big O.

please clarify

f(n) = Theta(g(n)), means

c1*f(n) <= g(n) <=c 2*f(n)

so basically g(n) is both upper bound and lower bound to f(n). hence whenever theta notation is given , big-oh and omega -oh are also meant.

Answer 2

This is a GATE 2016 question. https://gateoverflow.in/39581/gate2016-2-39

From the flow chart, you can see that, In worst case, We will have to call $A(n/2)$ $Five$ times. And in best case, Just Two times.

So, For Worst case time complexity, Recursive equation would be as follows :

$T(n) = 5T(\frac{n}{2}) + 1$

Now, Just apply Master's theorem :

$T(n) = \Theta(n^{log_2 \,5})$ (In worst case)

Hence, $\alpha = log_2\,5 = 2.32$