2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I can see three issues with what you have.

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

  2. $\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.

  3. 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.

$\endgroup$
  • $\begingroup$ I did drop the $-1$ since I was speaking in terms of theta notation, but you're probably right, I should have write equality only if I used the theta on the LHS. I don't really understand what was the first issue you mentioned. What's wrong with the outer sum? I can see that the inner sum is equal to $\frac{\sqrt{n}}{i}+1$ if that's what you mean. How do you suggest attacking iterative functions? Write $\sum$ for each loop and understand it's boundaries or maybe unfold the sum in a table? $\endgroup$ – Eran Feb 5 '14 at 8:29
  • $\begingroup$ @Quaker Translating loops into sums is what I'd do, no problem there. As for the outer sum, note that the number of iterations of any for-loop is a natural number but $\log(\sqrt{n})$ is not (always), so the sum can't be right. (All of these inaccurracies vanish in a $\Theta$ in the end, so some people may advise sloppiness for "clarity". I don't think that is fruitful, though.) $\endgroup$ – Raphael Feb 5 '14 at 8:31
  • $\begingroup$ I guess I should assume that $\sqrt{n}$ is of the form of $2^k$ $\endgroup$ – Eran Feb 5 '14 at 8:32
  • 1
    $\begingroup$ @Quaker: Why? Just use the exact number of iterations. (My answer includes a hint.) $\endgroup$ – Raphael Feb 5 '14 at 8:33
  • $\begingroup$ Is it possible to solve this iterative analysis by writing a table of the values that $i$ gets in each iteration and then the values that $j$ gets depending on $i$ and summing it all up? Would it work? $\endgroup$ – Eran Feb 5 '14 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.