Calm before the storm Pt 2

So the lectures given in the past 2 weeks have been somewhat confusing, ,mainly because I had to miss one of them in order to pick up my kendo gear over at the AC. Luckily, however, over the rest of the week I managed to get my facts straight and now I am confident in the new techniques that were taught, such as how to use unwinding, how to find closed-form solutions and how to find upper and lower bounds. Furthermore I have familiarized myself with Gauss' technique and now know how to effectively use the Master Theorem. Inadvertently I have also been studying for the upcoming term test! How nice it is to know that as a result of regular reviewing, I won't have to cram or study for extended periods of time for the test!

With assignment 2 now out of the way, I can focus on working on my 207 assignment 2 and my STA247 assignment 3. The storm has yet to arrive.

The interesting part of assignment 2 for 236 was the second question. Many of my friends were struggling to solve it and yet I did not understand why. I shall outline my procedure here in case any reader did not solve it.

So our problem involves binding a given T function and showing that it is bounded by big theta of lg(n). lg(n) is of course log(n) base 2. We first note that we have previously done similar questions involving ceilings and floors by substituting n for some power of 2 (2**k). So, it is natural to proceed similarly. Since we cannot assume n is a power of 2, let us bind it. Let n' be the smaller power of 2 larger than or equal to n where n is >= 2. So then it is clear that n'/2 < n <= n'.

Since we have proven that T is non-decreasing (this is an extremely easy proof to make so I will omit it), and we know that n <= n', then we can state that T(n) <= T(n'). Note that we now have our starting inequality - it should always involve T(n) and something that we can manipulate. So then using the definitions of T(n'), we have:
T(n) <= 1 + max{T(c(n'/2)), T(f(n'/2))}. Note that T is non-decreasing.
T(n) <= 1 + T(c(n'/2)). Note that (n'/2 = 2**(k-1)) is an integer so ceiling functions don't do anything.
T(n) <= 1 + T(2**(k-1)). Let us unwind the inequality n times.
T(n) <= k + T(2**(k-k)).
T(n) <= k + 1. Note that n' = 2**k, then k = lg(n').
T(n) <= lg(2n) + 1. Note that 2n > n'.
T(n) <= lg(2) + lg(n) + 1.
T(n) <= lg(n) + 2. Note that lg(n) > 1 since n >= 2. Set c = 4 or more.
T(n) <= 4*lg(n)
There is our upper bound. Letting b = 2, c = 4, then n >= b implies that T(n) <= c*lg(n).

Attempting the lower bound is very similar except we use n'/2 instead of n' since we know that n'/2 < n. Also note that n' < 2n. Then we have:
T(n) > T(n'/2)
T(n) > 1 + T((n'/2)/2) only if n'/2 >= 2 can this be possible, then n' >= 4 so n >= 4.
T(n) > 1 + T(2**(k-2))
T(n) > (k-1) + T(2**(k-1-(k-1))) through unwinding k-1 times.
T(n) > k - 1 + 1
T(n) > k
T(n) > lg(n'). Note that n' > n and lg function is always increasing.
T(n) > lg(n).

There is the lower bound. Letting b = 4, c = 1, then n >= b implies that T(n) <= c*lg(n).

Well bloggers, I am off to work on 207. Until next time,
-ラムダ