This is a written homework and it consists of the following exercises:
2.2 (found in textbook, page 64)
Suppose T1(N) = O(f(N)) and T2(N)
= O(f(N)). Which of the following are true?
a. T1(N) + T2(N) = O(f(N))
b. T1(N) - T2(N) = o(f(N))
c. T1(N) / T2(N) = O(1)
d. T1(N) = O(T2(N))
2.7 (textbook, page 64) For each of the following program fragments give an analysis of the running time (Big-Oh will do):
(2) sum = 0;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
sum++;
(4) sum = 0;
for (i=0; i<n; i++)
for (j=0; j<i; j++)
sum++;
(5) sum = 0;
for (i=0; i<n; i++)
for (j=0; j<i*i; j++) < change to j
for (k=0; k<j; k++)
sum++;
2.11 (textbook, page 66) An algorithm takes 0.5ms for an
input of size 100. How long will it take for an input size 500 if the
running time is the following (assume low-order terms are
negligible)?
a. linear
b. O(N log N)
c. quadratic
d. cubic
2.25 (textbook, page 64) Programs A and B are analyzed and
found to have worst-case running times no greater than 150 N
log2N and N2 respectively. Answer the following
questions, if possible:
a. Which program has the better guarentee on the running time,
for large values of N (N>10000)?
b. Which program has better guarentee on the running time, for
small values of N (N < 100)?
c. Which program will run faster on average for N =
1000?
d. Is it possible that program B will run faster than program A
on all possible inputs?
From the notes: Page 3-18, ex. 3-18 (the table it makes reference to is on page 3-9), 3-22, 3-24.