2
$\begingroup$

I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this:

public static int c(int n) {
    int i, j, s = 0;
    if (n > 1) {
        for(i = 0; i < n; i*=2) {
            for(j = n; j > 0; j/=2) {
                s++;
            }
            s+=c(n-2);
        }
    }
}

Now I have set the following recurrence equation: $T(n)=\log_2n*T(n-2)+\Theta(\log_2n)$

Now the height of the recurrence tree is $n/2$ so the $T(n) = n/2 * (\log_2n+\log_2n)=\Theta(n*\log_2n)$

The next procedure is this:

public static int d(int n, int m) {
    int i, j, k, ss = 0;
    if (n > 1) {
        for(i = 0; i < n; i++) {
            for(j = i; j > n; j+=2) {
                ss+=(i+1)-2*j+m;
            }
        }
        for(k=0; k<8; k++) {
            ss+=d(n/2, m/(k+1))
        }
    }
    return ss;
}

Again I have set this equation: $T(n, m)=8*T(n/2, m/(k+1))+\Theta(n^2)$

Now I think the $m$ parameter is not important because it is not used in for loop as a counter. Where $n/2$ gives us a recurrence tree of height $\log_2n$. So we get this: $T(n, m) = 8 * \log_2n*n^2=\Theta(n^2)$

I know that recurrence equations that I have set up are probably right, while the I am not sure about next steps.

$\endgroup$
  • 1
    $\begingroup$ You say that $8 \log n \cdot n^2 = O(n^2)$? How certain are you that that is correct? Can you prove it? $\endgroup$ – Pål GD Sep 4 '13 at 8:53
  • $\begingroup$ You might want to check out our reference questions and many of the questions about algorithm-analysis. $\endgroup$ – Raphael Sep 4 '13 at 9:23
3
$\begingroup$

Note that the first algorithm never terminates for $n>1$; it starts with $i=0$ and multiplies $i$ by $2$ in every iteration of the outer loop, so we never get $i \geq n$. I'll assume we start with $i=1$ instead.


I have some problems with your approach.

  1. What are you counting? Why?
  2. Where do the $\Theta$-terms in the recurrences come from? Don't you know better?
  3. Your $\Theta$-"arithmetic" is flawed. Please check your definitions and maybe our related reference questions.

To give you something to work with, let's look at your first algorithm. I say we count arithmetic operations and comparisons because they seem to be the most numerous (no other operations occur in the inner loop). Each loop translates to a sum, so we get

$\qquad\displaystyle T_c(n) = \sum_{i=0}^{\lfloor \log_2(n) \rfloor} 4 + T_c(n-2) + \sum_{j=0}^{\lceil \log_2(n) \rceil} 3$

and $T_c(0) = T_c(1) = 0$. You have to solve this recurrence; note that it contains a bit more detail than yours. If you throw such detail away, you should be very certain that this is justified (which is why professors do it all the time when appropriate). Such certainty comes only with practice, so you should work a few cases through rigorously.

First, you should simplify the sums. For the purpose of obtaining $\Theta$-bounds, you can work with upper and lower bounds on the recurrence. For instance, consider

$\qquad\displaystyle T_c^\leq(n) = (\log_2(n) + 1) \cdot (4 + T_c^\leq(n-2) + 3(\log_2(n) + 2))$ and

$\qquad\displaystyle T_c^\geq(n) = (\log_2(n) - 1) \cdot (4 + T_c^\geq(n-2) + 3\log_2(n))$

with the same anchors. If you get the same $\Theta$-bounds (or compatible $O$- and $\Omega$-bounds) from these, you have by $T_c^\geq(n) \leq T_c(n) \leq T_c^\leq(n)$ and squeeze theorem a $\Theta$-bound for your original recurrence.

Strategies for solving recurrences are already exhibited in detail in our reference question, so I'll leave that part to you.

$\endgroup$

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.