Recurrences using Substitution Method

Determine the positive number c & n0 for the following recurrences (Using Substitution Method):

1. T(n) = T(cei开发者_开发问答ling(n/2)) + 1 ... Guess is Big-Oh(log base 2 of n)

2. T(n) = 3T(floor(n/3)) + n ... Guess is Big-Omega (n * log base 3 of n)

3. T(n) = 2T(floor(n/2) + 17) + n ... Guess is Big-Oh(n * log base 2 of n).

I am giving my Solution for Problem 1:

Our Guess is: T(n) = O (log_2(n)). By Induction Hypothesis assume T(k) <= c * log_2(k) for all k < n,here c is a const & c > 0

     T(n) = T(ceiling(n/2)) + 1
<=>  T(n) <= c*log_2(ceiling(n/2)) + 1
<=>   "   <= c*{log_2(n/2) + 1} + 1
<=>   "    = c*log_2(n/2) + c + 1
<=>   "    = c*{log_2(n) - log_2(2)} + c + 1
<=>   "    = c*log_2(n) - c + c + 1
<=>   "    = c*log_2(n) + 1
<=>   T(n) not_<= c*log_2(n)      because c*log_2(n) + 1 not_<= c*log_2(n).

To solve this remedy used a trick a follows:

    T(n) = T(ceiling(n/2)) + 1
<=>  "  <= c*log(ceiling(n/2)) + 1 
<=>  "  <= c*{log_2 (n/2) + b} + 1             where  0 <= b < 1
<=>  "  <= c*{log_2 (n) - log_2(2) + b) + 1  
<=>  "   = c*{log_2(n) - 1 + b} + 1
<=>  "   = c*log_2(n) - c + bc + 1
<=>  "   = c*log_2(n) - (c - bc - 1)      if c - bc -1 >= 0  
                                             c >= 1 / (1 - b)
<=> T(n) <= c*log_2(n) for c >= {1 / (1 - b)}

so T(n) = O(log_2(n)).

This solution is seems to be correct to me ... My Ques is: Is it the proper approach to   do?

Thanks to all of U.

---

For the first exercise: We want to show by induction that T(n) <= ceiling(log(n)) + 1.

Let's assume that T(1) = 1, than T(1) = 1 <= ceiling(log(1)) + 1 = 1 and the base of the induction is proved.

Now, we assume that for every 1 <= i < nhold that T(i) <= ceiling(log(i)) + 1.

For the inductive step we have to distinguish the cases when n is even and when is odd.

If n is even: T(n) = T(ceiling(n/2)) + 1 = T(n/2) + 1 <= ceiling(log(n/2)) + 1 + 1 = ceiling(log(n) - 1) + 1 + 1 = ceiling(log(n)) + 1.

If n is odd: T(n) = T(ceiling(n/2)) + 1 = T((n+1)/2) + 1 <= ceiling(log((n+1)/2)) + 1 + 1 = ceiling(log(n+1) - 1) + 1 + 1 = ceiling(log(n+1)) + 1 = ceiling(log(n)) + 1

The last passage is tricky, but is possibile because n is odd and then it cannot be a power of 2.

---

Problem #1:

1. T(1) = t0
2. T(2) = T(1) + 1 = t0 + 1
3. T(4) = T(2) + 1 = t0 + 2
4. T(8) = T(4) + 1 = t0 + 3 ... T(2^(m+1)) = T(2^m) + 1 = t0 + (m + 1)

Letting n = 2^(m+1), we get that T(n) = t0 + log_2(n) = O(log_2(n))

Problem #2:

1. T(1) = t0
2. T(3) = 3T(1) + 3 = 3t0 + 3
3. T(9) = 3T(3) + 9 = 3(3t0 + 3) + 9 = 9t0 + 18
4. T(27) = 3T(9) + 27 = 3(9t0 + 18) + 27 = 27t0 + 81 ... T(3^(m+1)) = 3T(3^m) + 3^(m+1) = ((3^(m+1))t0 + (3^(m+1))(m+1)

Letting n = 3^(m+1), we get that T(n) = nt0 + nlog_3(n) = O(nlog_3(n)).

Problem #3:

Consider n = 34. T(34) = 2T(17+17) + 34 = 2T(34) + 34. We can solve this to find that T(34) = -34. We can also see that for odd n, T(n) = 1 + T(n - 1). We continue to find what values are fixed:

1. T(0) = 2T(17) + 0 = 2T(17)
2. T(17) = 1 + T(16)
3. T(16) = 2T(25) + 16
4. T(25) = T(24) + 1
5. T(24) = 2T(29) + 24
6. T(29) = T(28) + 1
7. T(28) = 2T(31) + 28
8. T(31) = T(30) + 1
9. T(30) = 2T(32) + 30
10. T(32) = 2T(33) + 32
11. T(33) = T(32) + 1

We get T(32) = 2T(33) + 32 = 2T(32) + 34, meaning that T(32) = -34. Working backword, we get

1. T(32) = -34
2. T(33) = -33
3. T(30) = -38
4. T(31) = -37
5. T(28) = -46
6. T(29) = -45
7. T(24) = -96
8. T(25) = -95
9. T(16) = -174
10. T(17) = -173
11. T(0) = -346

As you can see, this recurrence is a little more complicated than the others, and as such, you should probably take a hard look at this one. If I get any other ideas, I'll come back; otherwise, you're on your own.

EDIT:

After looking at #3 some more, it looks like you're right in your assessment that it's O(nlog_2(n)). So you can try listing a bunch of numbers - I did it from n=0 to n=45. You notice a pattern: it goes from negative numbers to positive numbers around n=43,44. To get the next even-index element of the sequence, you add powers of two, in the following order: 4, 8, 4, 16, 4, 8, 4, 32, 4, 8, 4, 16, 4, 8, 4, 64, 4, 8, 4, 16, 4, 8, 4, 32, ...

These numbers are essentially where you'd mark an arbitary-length ruler... quarters, halves, eights, sixteenths, etc. As such, we can solve the equivalent problem of finding the order of the sum 1 + 2 + 1 + 4 + 1 + 2 + 1 + 8 + ... (same as ours, divided by 4, and ours is shifted, but the order will still work). By observing that the sum of the first k numbers (where k is a power of 2) is equal to sum((n/(2^(k+1))2^k) = (1/2)sum(n) for k = 0 to log_2(n), we get that the simple recurrence is given by (n/2)log_2(n). Multiply by 4 to get ours, and shift x to the right by 34 and perhaps add a constant value to the result. So we're playing around with y = 2nlog_n(x) + k' for some constant k'.

Phew. That was a tricky one. Note that this recurrence does not admit of any arbitary "initial condiditons"; in other words, the recurrence does not describe a family of sequences, but one specific one, with no parameterization.