Question 9787 – Database-Management-System
November 24, 2023Question 11888 – UGC NET CS 2014 Dec – paper-3
November 25, 2023Question 8141 – Algorithms
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α), then the least possible value (accurate upto two decimal positions) of α is _________.
Correct Answer: A
Question 26 Explanation:
This type of problem, we have to consider worst case time complexity, it mean that all possibilities.
According to flow chart total 5 worst case possibilities of function calls.
The remaining function calls/return statements will execute only constant amount of time.
So, total function calls 5.
The Recurrence will be
A(n) = 5A(n/2) + O(1)
Apply Master’s theorem,
A=5, b=2, k=0, p=0
a > bk case
A(n) = n(logba ) = n(log25) = n2.3219280
∴α = 2.3219280
According to flow chart total 5 worst case possibilities of function calls.
The remaining function calls/return statements will execute only constant amount of time.
So, total function calls 5.
The Recurrence will be
A(n) = 5A(n/2) + O(1)
Apply Master’s theorem,
A=5, b=2, k=0, p=0
a > bk case
A(n) = n(logba ) = n(log25) = n2.3219280
∴α = 2.3219280
2.3219280
2.3219281
2.3219282
2.3219283
Subscribe
Login
0 Comments