Register

GO Classes DPP | Algorithms | Recurrence Relation

382 views
2 2 votes

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 following is the worst-case time complexity of this algorithm?

(Here $\Theta$ represents big-theta.)

  1. $\Theta(n)$
     
  2. $\Theta(n \log n)$
     
  3. $\Theta\!\left(n^{\log_{3} 5}\right)$
     
  4. $\Theta\left(n^2\right)$

2 Answers

Best answer
1 1 vote

$$
T(n)=5 T(n / 3)+O(n)
$$


By Master's Theorem:

  • $\mathrm{a}=5, \mathrm{~b}=3, \mathrm{f}(\mathrm{n})=\mathrm{n}$
     
  • $\mathrm{n}^{\log _3 5} \approx \mathrm{n}^{1.464}$
     
  • $\mathrm{n}=\mathrm{O}\left(\mathrm{n}^{1.464}\right)$
     
  • case 1 applies

Correct Answer: $\Theta\left(\mathrm{n}^{\log _3 5}\right)$

• selected by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | Alg...Next → · GO Classes DPP | Alg...
← Previous in category · GO Classes DPP | Alg...Next in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

1 1 vote
3 answers 3 answers
536
536 views
GO Classes asked Aug 23, 2025
536 views
GO Classes DPP | Algorithms | Recurrence Relation
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 eq...
2 2 votes
2 answers 2 answers
477
477 views
GO Classes asked Aug 23, 2025
477 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} ) ...
1 1 vote
3 answers 3 answers
400
400 views
GO Classes asked Aug 23, 2025
400 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
457
457 views
GO Classes asked Aug 23, 2025
457 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...