Mergesort is an example of divide-and-conquer strategy. Divide a problem into subproblems until getting to the smallest one (when there is one element in the array for mergesort) and then combine solutions of subproblems together.
The time complexity for divide-and-conquer problems is a little complicated and so is the proof of it. For example, in mergesort, T(n) = 1 if n = 1, and T(n) = T(ceiling of n/2) + T(floor of n/2) + dn if n > 1. Though the expression is long, it's based on the algorithm of mergesort and I find it easy to remember if understanding the algorithm.
To prove the time complexity of mergesort which is upper bounded by n*lgn, it is more difficult than proofs before in the course. Here, I need three steps. First, I need to find out the expression for T(n) when n = 2^k (k is a natural number) and using induction to prove it. Then I need to show that T(n) is monotonic (non-decreasing actually) also using induction. At last, I use the previous result to prove that T(n) < Xn*lgn. But at this point, another difficulty comes out. I have to figure out what X is. So I can make T(n) bigger to the expression in the form n *lgn times another coefficient, which is the X I want. After all that, I can say T(n) is upper bounded by n *lgn.
For time complexity of other divide-and-conquer problems, the steps are similar. The difference is that they are not necessarily divided into two parts, instead, to pieces of size n/b parts. There's really a lot of work, but generally, I need to remember three things:
1. Find out the expression for T(n) when n = b^k (k is a natural number)
2. Prove T(n) is monotonic.
3. Prove the time complexity using previous results.
Monday, October 20, 2008
Saturday, October 18, 2008
unwind recursion formula
Though recursion formulas are defined based on previous ones, like Fibonacci numbers, F(n) = F(n-1) + F(n-2), for natural numbers n > 2, the formula can be expressed only depending on current variables, which is the closed form for F(n).
To get the closed form, we need to unwind the formula given recursively. What we do is use the formula continuously until we hit the base case, whose value is given explicitly. For example, in time complexity for binary search, T(n) = 3 for n = 1, and T(n) = 3 + T(n/2) for other natural numbers. We unwind T(n) until we get to T(1). So T(n) = 3 + T(n/2) = 3 + 3 + T(n/4) = ... = 3lgn + T(1) = 3lgn + 3. Thus, we get the closed form for time complexity of binary search.
A special case occurs in Fibonacci numbers. Each element of Fibonacci numbers seems like r^n. Because F(n) = F(n-1) + F(n-2), so r^2 = r^1 + r^0. we can get two roots r1, r2 from the equation and for any a, b, ar1 + br2 also satifies the equation. As F(n) = n for n < 2, ar1 + br2 = 0 and ar1 + br2 = 1. Then we get a and b. Thus, we get the closed form for F(n).
To get the closed form, we need to unwind the formula given recursively. What we do is use the formula continuously until we hit the base case, whose value is given explicitly. For example, in time complexity for binary search, T(n) = 3 for n = 1, and T(n) = 3 + T(n/2) for other natural numbers. We unwind T(n) until we get to T(1). So T(n) = 3 + T(n/2) = 3 + 3 + T(n/4) = ... = 3lgn + T(1) = 3lgn + 3. Thus, we get the closed form for time complexity of binary search.
A special case occurs in Fibonacci numbers. Each element of Fibonacci numbers seems like r^n. Because F(n) = F(n-1) + F(n-2), so r^2 = r^1 + r^0. we can get two roots r1, r2 from the equation and for any a, b, ar1 + br2 also satifies the equation. As F(n) = n for n < 2, ar1 + br2 = 0 and ar1 + br2 = 1. Then we get a and b. Thus, we get the closed form for F(n).
recursion at a glance
Recursion is something like you have established a foundation and other situations are built from it. For example, in Fibonacci numbers, F(n) = n for natural numbers n < 2, which serves as a foundation and for other natural numbers, F(n) = F(n-1) + F(n-2).
Recursion can be used to break large and complex problems step by step to the smallest ones. As in binary search in a sorted array, the problem is broken down by half each time until you only have two elements to compare at last. And in mergesort, the idea is to divide the array into two parts from the middle, and then again divide each part from the middle. You keep dividing parts into two until you get an array of size one, which you don't need to sort further, but instead, you just return the element. Then you combine the sorted left and right parts into one sorted part and at last, you end up having the whole array sorted.
Recursion can be used to break large and complex problems step by step to the smallest ones. As in binary search in a sorted array, the problem is broken down by half each time until you only have two elements to compare at last. And in mergesort, the idea is to divide the array into two parts from the middle, and then again divide each part from the middle. You keep dividing parts into two until you get an array of size one, which you don't need to sort further, but instead, you just return the element. Then you combine the sorted left and right parts into one sorted part and at last, you end up having the whole array sorted.
Subscribe to:
Posts (Atom)