Question:
The recurrence T(n) = 2T(n/2) + n has a solution of _______.
The recurrence T(n) = 2T(n/2) + n has a solution of _______.
Show Hint
For divide and conquer recurrences, master theorem can be used to determine the complexity quickly.
Updated On: Jun 16, 2025
- O(n)
- O(nlogn)
- O(n²)
- O(logn)
Show Solution
Verified By Collegedunia
The Correct Option is B
Solution and Explanation
The given recurrence is a divide and conquer recurrence, and it can be solved using the master theorem. The solution to this recurrence is O(nlogn), as it fits the second case of the master theorem.
Was this answer helpful?
0
0
Top AP PGECET Computer Science & Information Technology Questions
- The number of multiplications needed to find $ x^{32} $ when $ x $ is given, is
- How many terms will there be in the expansion of $ (x + y + z)^5 $?
- How many 5-digit numbers can be formed with the digits 0, 1, 2, 3, 4, with no digit being repeated?
- What is the generating function for $ a_r $, where $ a_r $ is the number of integral solutions for the equation $$ a + b + c = r \quad \text{with} \quad 0 \leq a, b, c \leq 3? $$
- What is the value of $ f(5) $ where $ f(n) $ is recursively defined as $ f(n) = n \times (n-1) $ for $ n>1 $ and $ f(1) = 2 $?
View More Questions
Top AP PGECET Data Structures Questions
- What is the data structure used for converting a recursive program into the non-recursive version of the same?
- How much memory is required to store the elements of the array defined as float items[4][5][6];
- What is the maximum number of binary trees possible with 4 nodes?
- A one-dimensional array has n elements stored from 0th position to (n-1)th position. How many elements need to be moved to insert an element at pth position of the array?
- Which one of the following statements is true?
View More Questions
Top AP PGECET Questions
- If 125V is applied across a 250V, 100W incandescent bulb, the power consumed will be _____ .
- The power consumed by a coil is 300 watts when connected to a 30V DC source and 108 watts when connected to a 30V AC source. The reactance of the coil is ____ .
The supply voltage magnitude \( |V| \) of the circuit shown below is ____ .
A two-port network is defined by the relation
\(\text{I}_1 = 5V_1 + 3V_2 \)
\(\text{I}_2 = 2V_1 - 7V_2 \)
The value of \( Z_{12} \) is:- Which of the following theorems is the dual of Norton’s theorem?
View More Questions