What is the complexity of T(n) = 2T(n/4) + n^2 \log n? (i) \Theta(n^2

Back to the 2023 paper

Module 1: Introduction

20232m

What is the complexity of $T(n) = 2T(n/4) + n^2 \log n$ ?
(i) $\Theta(n^2 \log(\log n))$
(ii) $\Theta(n^3 \log n)$
(iii) $\Theta(n^2 \log n)$
(iv) $\Theta(n \log n)$

Search Google Ask AI

Worked SolutionAI Assisted

Answer: (iii) Θ(n² log n)

Master: a=2,b=4, n^{log_b a}=n^{0.5}. f=n² log n dominates → case 3 → Θ(f)=Θ(n² log n). Regularity holds.

Similar questions

Design and Analysis of Algorithms The recurrence T(n) = T(n/2) + 1 has a time complexity of: (i) O(n) (ii) O(\log n) (iii) O(n \log n) (iv) O(n^2)20242m Design and Analysis of Algorithms If an algorithm has time complexity T(n) = 5n^2 + 3n + 7, its asymptotic upper bound is: (i) O(n) (ii) O(n^2) (iii) O(n \log n) (iv) O(n^3)20242m Design & Analysis of AlgorithmsThe complexity of binary search algorithm is: - (i) O(n) - (ii) O(\log n) - (iii) O(n^2) - (iv) O(n \log n)20192m Design and Analysis of Algorithms Apply the Master Theorem to determine the time complexity of the following recurrence relations. (i) T(n) = 4T(n/2) + n^3 (ii) T(n) = T(n/2) + 2^n20235m

PreviousWhich sorting algorithm is considered stable and has a time complexity of O(n^2)? (i) Quick sort (ii) Merge sort (iii) Insertion sort (iv) Selection sort NextIn algorithm analysis, what does "space complexity" refer to? (i) The number of input elements (ii) The amount of physical memory used (iii) The number of recursive calls (iv) The number of lines of code in the algorithm

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.

Try Coursify Free