Exams › GATE › Engineering Mathematics

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(n) = 2T(n/2) + log n

1. Θ(n)
2. Θ(n log n)
3. Θ(n²)
4. Θ(log n)

Correct answer: Θ(n)

Solution

Here a=2, b=2, so n^(log_b a)=n. Since f(n)=log n = O(n^(1-e)), Master theorem case 1 applies and T(n)=Theta(n). The answer is Theta(n), not Theta(n log n).

Related GATE Engineering Mathematics questions

• The smallest positive root of the equation x⁵ - 5x⁴ - 10x³ + 50x² + 9x - 45 = 0 lies in the range
• For a flowing fluid, a dimensionless combination of velocity (V), length scale (l), and acceleration due to gravity (g) would be
• The second derivative of a function f is computed using the fourth-order Central Divided Difference method with a step length h. The CORRECT expression for the second derivative is
• In the IEEE floating point representation the hexadecimal value 0x00000000 corresponds to
• Let r denote number system radix. The only value(s) of r that satisfy the equation √121_r = 11_r, is/are
• The Newton-Raphson iteration xₙ₊₁ = 1/2 (xₙ + R/xₙ) can be used to compute the

⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →