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* ![]() |
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
.