GATE 2016 CS (CS2) – Question 49

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Numerical answer

The flowchart defines recursive function A(n). Other statements cost O(1). If worst-case time is $O(n^\alpha)$, find the least α to two decimal places.

Diagram for GATE 2016 CS (CS2) question 49

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 2.2 to 2.4

Explanation

The longest execution path calls A(n/2) six times: twice initially, twice along the middle branch, once below, and once on the final left branch. Hence $T(n)=6T(n/2)+O(1)$. The master theorem gives $\alpha=\log_2 6=2.58496$, rounded 2.58.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2017 CS (CS2) Q13 – Match (P) Towers of Hanoi with n disks, (Q) binary search on n sorted numbers, (R)…
GATE 2017 CS (CS2) Q40 – T(n)=2T( n)+1 for n>2, and T(n)=2 for 0<n≤2. Find its asymptotic order.
GATE 2017 CS (CS2) Q48 – Find the time complexity.
GATE 2012 CS (CS1) Q15 – Find the worst-case search time in a balanced BST with n2n elements.
GATE 2012 CS (CS1) Q28 – W(n) and A(n) are worst-case and average running times on inputs of size n. Which always…
GATE 2013 CS (CS1) Q40 – How many elements can heap sort sort in ( n) time?

All Asymptotic Analysis and Time/Space Complexity questions →