[Solved]: Finding asymptotically tight bounds $\Theta$ of two procedures

Problem Detail: 

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.

Asked By : Jernej Jerin

Answered By : Raphael

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.

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents