**Problem Detail:**

I want to analyze the runtime of this algorithm:

`int fun (int arr[], int n) { int result = 1; int i, j; if (n == 1) return 1; else { result = fun(arr, 2n/3); for (i = 1; i <= sqrt(n); i=i*2); for (j=0; j<sqrt(n)/i; j++) result += arr[j]; return result; } } `

I can see that the runtime recurrence should be something like

$\qquad\displaystyle T(n) = T\left(\frac{2n}{3}\right) + \Theta(X)$

where $X$ is the time of the extra operations per recursion.

I can also see that the extra operations are:

$\qquad\begin{align*} \sum_{i=1}^{\log(\sqrt{n})} \sum_{j=0}^{\frac{\sqrt{n}}{i}}1 &= \sum_{i=1}^{\log(\sqrt{n})}\frac{\sqrt{n}}{i} \\ &= \sqrt{n} \cdot \sum_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \\ &= \sqrt{n}\cdot \log(\log(\sqrt{n})) \end{align*}$

So all in all:

$\qquad\begin{align*} T(1) &= 1 \\ T(n) &= T\left(\frac{2n}{3}\right) + \sqrt{n}\cdot \log(\log(\sqrt{n})) \end{align*}$

But I could not continue from here to solve this recursion.

###### Asked By : Eran

#### Answered By : Raphael

I can see three issues with what you have.

There are some inaccurracies in your sums. The outer one needs rounding of the upper boundary, the inner needs a $-1$.

$\displaystyle \sum_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \neq \log(\log(\sqrt{n}))$

The true value of the sum is $H_{\log(\sqrt{n})}$ (will change slightly if you fix the sums). It's true that the difference vanishes in $\Theta$ if you go that route, but better not write equality where it does not hold.

You dropped the recursion at the end! You should have

$\qquad \displaystyle T(n) = T(2/3 \cdot n) + \dots$

From there, unfold the recurrence:

$\qquad\begin{align*} T(n) &= T(2/3 \cdot n) + f(n) \\ &= T(4/9 \cdot n) + f(2/3 \cdot n) + f(n) \\ &\dots \end{align*}$

Spot a pattern, guess the solution and prove it correct by induction! This part is well covered by our reference question in case you have trouble.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21311

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback