CSE 5311 Spring 1998
Homework #1
Due: February 4, 1998
Search(A, k, p, r) COST TIMES i = p 1 1 while ((A[i] <> k) and (i <= r)) 1 t1+1 i = i + 1 1 t1 if i <= r 1 1 then return i 1 1 else return -1 1 1
Best Case T(n) = 1 + 2 + 1 + 1 + 1 + 1 = 7 =
Worst Case T(n) = 1 + (n+1) + n + 1 + 1 + 1 = 5 + n*(2) =
Search(A, k, p, r) COST TIMES if (p <= r) 1 1 then i = (p+r)/2 1 t1 if (k == A[i]) 1 t1 then return i 1 t1*t2 else if (k < A[i]) 1 t1*(1-t2) then Search(A, k, p, i) T(n/2) t1*(1-t2)*t3 else Search(A, k, i+1, r) T(n/2) t1*(1-t2)*(1-t3) else return -1 1 1-t1
Master method: a=1, b=2, f(n) = 4 = . This is case 2 because = 0. Thus T(n) = Theta(lgn).
n | f(n) = lg n | f(n) = n | f(n) = n lg n | f(n) = | f(n) = |
10 | 3.3s | 10s | 33.0s | 100s | 1024s |
20 | 4.3s | 20s | 86s | 400s | 291h |
50 | 5.6s | 50s | 280s | 2500s (= 41.7min) | 357,020 centuries |
100 | 6.6s | 100s | 660s (= 11min) | 10,000s (= 2.78h) | 4* centuries |
1,000 | 9.96s | 1,000s | 9960s (= 2.76h) | 277.78h | *** |
10,000 | 13.3s | 10,000s (= 167min) | 133000s (= 36.9h) | 1,157 days | *** |
No. In order for to be O( ), we would have to find c and such that for all n >= . Dividing each term by n, we see that we would need , which for any constant c will not be met as n grows beyond the value of c.
Yes. In order for to be ( ), we need to find c and such that for all n >= . Dividing each term by n yields , which is true for c = 1 and = 1.
n! |
Arranged left-to-right as slowest to fastest growth rate we get
n! |
Master
a=2, b=2, f(n) = , = 1. This is case 3 with = 2. We need to show that 2f(n/2) <= cf(n) for c<1 and sufficiently large n. Show that 2*( ) <= c* , or 2( ) <= c , 1/4 <= c , which is true for c=1/2.
Thus T(n) = .
Iteration
T(n) = + 2T(n/2)
= + 2( + 2T(n/4))
= + 2( + 2( + 2T(n/8)))
= + + 4( + 2T(n/8)))
The ith term is and the boundary case is reached when
= 1, i >= .
=
or
+
= =
= O( )
Iteration
The recursion will terminate when the argument to T() equals 1, i.e., n-2i = 1 or i = (n - 1)/2.
Substitution
First, show using the inductive hypothesis .
Unfortunately, we cannot discard the without decreasing the righthand side and violating the inequality. So, we choose a different member of for T(n); namely, , where b is a constant. The inductive hypothesis is now .
given that , or . Since this is a valid constant, .
Next, show using the inductive hypothesis .
since we can subtract from the righthand side without violating the inequality. Therefore, , and .
Master
a=3, b=3, f(n) = , = 1. This is case 1 where = 1. T(n) = .
Iteration
The recursion will terminate when the argument to T() equals 1, i.e., , or , or .
Substitution
First, show using the inductive hypothesis .
Unfortunately, we cannot discard the without decreasing the righthand side and violating the inequality. So, we choose a different member of O(n) for T(n); namely, , where b is a constant. The inductive hypothesis is now .
given that , or . Since this is a valid constant, T(n) = O(n).
Next, show using the inductive hypothesis .
The last step is valid since we can always reduce the righthand side of the inequality. Therefore, , and .