edited by
16,239 views
61 votes
61 votes

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

edited by

2 Answers

Best answer
103 votes
103 votes
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$
edited by
9 votes
9 votes

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$

Answer:

Related questions

49 votes
49 votes
8 answers
3