Register

GO Classes DPP | Algorithms | Recurrence Relation

• edited by
1 flag 460 views
2 2 votes

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} )
        doconstantwork() // O(1)
        return (DoSomething (floor (sqrt(n))) + n);
}

 

  1. $\Theta(n \log n)$  

  2. $\Theta(\sqrt{\log n})$

  3. $\Theta(\log n)$  

  4. $\Theta(n)$  

  • 🚩 Edit necessary | 👮 Rhino | 💬 “semicolon missing in line 6”

2 Answers

Best answer
2 2 votes

$\mathrm{T}(\mathrm{n})=\mathrm{T}(\sqrt{n})+\sqrt{\log n}$.

Solution sketch:

  • Let $\mathrm{n}=2^{\mathrm{m}} \rightarrow \mathrm{T}\left(2^{\mathrm{m}}\right)=\mathrm{T}\left(2^{\mathrm{m} / 2}\right)+\sqrt{m}$.
     
  • Let $\mathrm{S}(\mathrm{m})=\mathrm{T}\left(2^{\mathrm{m}}\right)$

    then

$$
\mathrm{S}(\mathrm{~m})=\mathrm{S}(\mathrm{~m} / 2)+\sqrt{m}
$$


Expansion:

$$
\mathrm{S}(\mathrm{~m})=\sqrt{m}+\sqrt{m / 2}+\sqrt{m / 4}+\cdots
$$

  • This behaves like a decreasing geometric series scaled by $\sqrt{m}$
     
  • So total $=\Theta(\sqrt{m})$
     
  • Back-substitute $m=\log n$

$$
\mathrm{T}(\mathrm{n})=\Theta(\sqrt{\log n}) .
$$

• 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
520
520 views
GO Classes asked Aug 23, 2025
520 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
365
365 views
GO Classes asked Aug 23, 2025
365 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
385
385 views
GO Classes asked Aug 23, 2025
385 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
440
440 views
GO Classes asked Aug 23, 2025
440 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...