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

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 α is ________.

 first it asks for worst case time complexity then i take the path which contains 5 times A(n/2)

 but it then saying least possible value then i choose 2 times A(n/2). isn’t the question be ambiguous. Anyone help if I’m not getting it right... 

---

Worst case means the worst input – not the worst algorithm.

---

Worst case means the worst input – not the worst algorithm.

this I’m able to understand like if i give array in reverse sorted in insertion sort then it give worst case for giving worst input.

Worst case means the worst input – not the worst algorithm.

 Sir, what do you mean by this. how algorithm can be worst…??

---

yes exactly. Or like you did choose the longest path in the flow chart which will correspond to the worst case input.

Now why they told “the least possible value” – is because of the definition of big-O. You can read that from a standard resource like Cormen – I have heard many youtube videos explaining it as for worst case and that is what the majority of GATE aspirants also believe.

---

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