Register

GO Classes DPP | Algorithms | Recurrence Relation

542 views
1 1 vote
Consider the following recurrence relation:

$$
\mathrm{T}(\mathrm{n})=\sqrt{n} \cdot \log \mathrm{n}+\mathrm{T}(\mathrm{n} / 2), \mathrm{T}(1)=1
$$

The above recurrence is equivelant to: $T(n)=\theta\left(n^a \cdot \log ^b n\right)$
The value of $a+b$ is (upto 2 decimal places) _________ .

3 Answers

Best answer
1 1 vote
$\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n} / 2)+\sqrt{n} \log \mathrm{n}, \mathrm{T}(1)=1$.

case-3 of master theorem applies, hence $T(n)=\theta(\sqrt{n} \log n)$

So $a=1 / 2, b=1->a+b=(1 / 2)+1=1.5$
 
• selected by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | Alg...Next → · Query About DPP Play...
← Previous in category · GO Classes DPP | Alg...Next in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

2 2 votes
2 answers 2 answers
484
484 views
GO Classes asked Aug 23, 2025
484 views
GO Classes DPP | Algorithms | Recurrence Relation
What is the time complexity of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else for( i=1 to sqrt{log n} ) ...
2 2 votes
2 answers 2 answers
386
386 views
GO Classes asked Aug 23, 2025
386 views
GO Classes DPP | Algorithms | Recurrence Relation
Consider the following program:function GO_Recursion(n): if n <= 1: return for i=1 to n: doConstantWork() // O(1) for j=1 to 5: GO_Recursion(n/3)Which of the ...
1 1 vote
3 answers 3 answers
401
401 views
GO Classes asked Aug 23, 2025
401 views
GO Classes DPP | Algorithms | Recurrence Relation
Solve the following recurrences.$$T(n)=2 T(n-2), T(0)=1, T(1)=1 .$$(Here $\Theta$ represents big-theta.)$\Theta\left((\sqrt{ 2})^n\right)$ $\Theta\!\left(\sqrt{2^n}\right...
1 1 vote
3 3 answers
463
463 views
GO Classes asked Aug 23, 2025
463 views
GO Classes DPP | Algorithms | Recurrence Relation
Suppose that the function F is defined for all powers of $2$ and is described by the following recurrence equation and base case: $F(n)=n-2+2 F(n / 2), F(1)=1$ respective...