User:Lokyung/sandbox

When analyzing algorithms, we only care about the asymptotic behavior. Rather than solving exactly the recurrence relation associated with the cost of an algorithm, it is sufficient to give an asymptotic characterization. The main tool for doing this is the Master Theorem.

Introduction

Let T(n) be a monotonically increasing function that satisfy:

$T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)$

$T(1)=c$

${\mbox{where}}\;\;a\geq 1{\mbox{, }}b>1{\mbox{, }}c>0$

In the application to the analysis of a recursive algorithm, the constants and function take on the following significance:

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
• f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

If $f(n)$ is $\Theta \left(n^{d}\right)$ where $d>=0$ then:

$T(n)=\Theta \left(n^{d}\right)\;\;\;\;\;\;\;{\mbox{if }}a<b^{d}$

$T(n)=\Theta \left(n^{d}\log n\right)\;\;\;\;\;\;\;{\mbox{if }}a=b^{d}$

$T(n)=\Theta \left(n^{\log _{b}a}\right)\;\;\;\;\;\;\;{\mbox{if }}a>b^{d}$

Master Theorem: Pitfalls

You cannot use the Master Theorem if

• $T(n)$ is not monotone, example: $T(n)=sin(x)$
• $f(n)$ is not a polynomial, example: $T(n)=2T({\frac {n}{2}})+2^{n}$
• $b$ cannot be expressed as a constant, example: $T(n)=T({\sqrt {n}})$

Note that the Master Theorem does not solve the recurrence equation.

Example

Case 1:

Let $T(n)=T({\frac {n}{2}})+{\frac {1}{2}}n^{2}+n$

What are the parameters?

$a=1$

$b=2$

$d=2$

Therefore, which condition applies?

$1<2^{2},{\mbox{case 1 applies}}$;

We conclude that

$T(n)\in \Theta \left(n^{d}\right)=\Theta (n^{2})$

Now let's see if this make sense

Assume $T(1)=1$

$T(2)=T({\frac {2}{2}})+{\frac {1}{2}}(2)^{2}+2$

$T(2)=1+2+2=5$

$T(4)=T({\frac {4}{2}})+{\frac {1}{2}}(4)^{2}+4$

$T(4)=5+8+4=17$

$T(8)=T({\frac {8}{2}})+{\frac {1}{2}}(8)^{2}+8$

$T(8)=17+32+8=57$

$T(16)=T({\frac {16}{2}})+{\frac {1}{2}}(16)^{2}+16$

$T(16)=8+128+16=152$

Indeed, $T(n)=\Theta (n^{2})$

Case 2:

Let $T(n)=2T({\frac {n}{4}})+{\sqrt {n}}+42$

What are the parameters?

$a=2$

$b=4$

$d={\frac {1}{2}}$

Therefore, which condition applies?

$2=4^{\frac {1}{2}},{\mbox{case 2 applies}}$;

We conclude that

$T(n)\in \Theta \left(n^{d}\log n\right)=\Theta (\log n{\sqrt {n}})$

Case 3:

Let $T(n)=3T({\frac {n}{2}})+{\frac {3}{4n}}+1$

What are the parameters?

$a=3$

$b=2$

$d=1$

Therefore, which condition applies?

$3>2^{1},{\mbox{case 3 applies}}$;

We conclude that

$T(n)\in \Theta \left(n^{\log _{b}a}\right)=\Theta (n^{\log _{2}3})$

${\mbox{Note that }}\log 23\approx 1.584...{\mbox{, can we say that }}T(n)\in \Theta (n^{1.584})$

${\mbox{No, because }}\log 23\approx 1.5849...{\mbox{ and }}n^{1.584}\notin \Theta (n^{1.5849})$

Application to common algorithms

Algorithm	Recurrence Relationship	Run time	Comment
Binary search	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Apply Master theorem case $c=\log _{b}a$, where $a=1,b=2,c=0,k=0$
Binary tree traversal	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Apply Master theorem case $c<\log _{b}a$ where $a=2,b=2,c=0$
Optimal Sorted Matrix Search	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$O(n)$	Apply Akra-Bazzi theorem for $p=1$ and $g(u)=\log(u)$ to get $\Theta (2n-\log n)$
Merge Sort	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Apply Master theorem case $c=\log _{b}a$, where $a=2,b=2,c=1,k=0$

Thomas H. Cormen

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Clifford Stein. He has a new book out called Algorithms Unlocked. He is a Full Professor of computer science at Dartmouth College and currently Chair of the Dartmouth College Department of Computer Science. Between 2004 and 2008 he directed the Dartmouth College Writing Program.

Thomas H. Cormen was born in New York City in 1956. He grew up in Oceanside, New York. He received his bachelor's degree in Electrical Engineering and Computer Science from Princeton University in June 1978. He then went to Massachusetts Institute of Technology, where he earned his master's degree in Electrical Engineering and Computer Science in May 1986 and his PhD in 1993.

Thomas's personal life ( off his website )

My wife, Nicole, and I took a Barbecue tour of the South in August 1998.

In July 2010, I rollerbladed the Trail of the Coeur D'Alenes, a 71.4-mile-long paved rail trail in the Idaho panhandle. Accompanied by my friend, Paul Daro, who also bladed, and Nicole, who biked, we went 42 miles the first day and the balance the second day. Here is a photo of the three of us at the start of the first day, at the western trailhead in Plummer, Idaho, (on the Coeur D'Alene reservation) and here is a photo of Paul and me at the start of the second day, at the eastern trailhead in Mullan, Idaho. We met this fellow on the trail during the first day. This page has some rough videos that Paul took.

My brother-in-law, Tony Pecora, is the first patient in the US to undergo the Edmonton Protocol for treatment of juvenile diabetes. Check out his website at http://www.isletsupporter.com.

I was the Ice Man for the Maryland State Barbecue Championship in 2003, 2004, and 2005. Here's a photo from the 2005 contest of me with a quad-runner full of 40-pound bags of ice. The photo was taken by the Dizzy Pigs, the 2005 and 2006 Grand Champions. Even with the megaphone, I was pretty hoarse by the end of the second day. The Dizzy Pigs, and all the other contestants, can explain why.

I was Kansas City Barbeque Society Certified Barbeque Judge number 62145. (I have purposely let my KCBS membership lapse.) My first contest as a certified judge was the 2011 Maryland State Championship in Bel Air. Here is a photo of me just starting to judge the first item, chicken. And here is a photo after judging five entries each of chicken, pork ribs, pork, and beef brisket. (Photos courtesy of Craig Ward, a.k.a. "Mr. Time To Go," a.k.a. "Large And In Charge," the contest organizer.)

In September 1997, Nicole and I finished hiking all 48 of the 4000-foot peaks in the White Mountains of New Hampshire.

A former student wrote an article for USA Hockey about the time I was "that guy." (The photo in the article is not of me. Goalies have all their teeth.)

Have you ever noticed something odd about bank deposit slips?

When is a door not a door?