CS124 HW #1

input: int Array[n], int v
output: int i for v=A[i] or NIL
bool found = false;
int i=0;

while(i<=n && !found)
{
   if (A[i] == v)
      found = true;
   else
      i++;
}

   if (found)
     return i;
   else
     return NIL;
}

a) 1/n (Sum i=1 to n of i) = 1/n (n(n+1)/2) = n+1/2 (ave. # of elements)

b) n (worst case: all elements checked)

c) worst case theta(n)
   average cae theta(n); for very large n, the constant is not significant

bsearch (int Array[n], int v, int i, int n);
{
   int p;
   while (i <= n)
   {
      mid = (i + n )/2
      if (x < Array[mid])
	 n = mid-1;
      else if (x > Array[mid])
	 i = mid + 1;
      else return mid;
   }

   return -1;


}

The worst case running time for the above algorithm is theta(lgn).
The algorithm takes lgn steps to complete and at each step a 
constant number of operations are performed.

a) 8n^2 < 64nlgn
   n < 8 lgn
   2^n/8 

[10] Problem 2.1-8 pg 32

  
a) omega(g(n,m)) = {f(n,m): there exists positive constants c, n0, m0 such
   that: 0 <= cg(n,m) <= f(n,m) for all n > n0 and m > m0

b) theta(g(n,m) = {f(n,m): there exists positive constants, c1, c2, n0,m0
   such that 0 <= c1g(n,m) <= f(n,m) <= c2g(n,m) for all n>n0 and
   m > m0



[10] Problem 8.2-3 pg 160

 Given that the lists are partially sorted, insertion sort will perform
 better than quicksort. When the list is almost sorted, the inner loop
 of insertion sort will not always be executed. This leads to a running
 time which approaches theta(n).

 Quicksort on the other hand performs badly when the list is sorted. For
 a sorted list, the do loops are executed n times. Therefore for sorted
 lists quicksort running time approaches O(n^2).

 
[10] Problem 8.2-4 pg 160
The minimum depth takes n*alpha^m. m is the number of iterations it takes
to get to a leaf node
   n*alpha^m = 1
   alpha^m = 1/n
   mlg(alpha) = -lgn
   m = -lgn/lg(alpha)

Maximum
   n*(1-alpha)^M = 1
   (1-alpha)^M = 1/n
   Mlg(1-alpha) = -lg n
   M = -lgn/lg(1-alpha)


[15] Solve the recurrence relation: T(n) = T(n-a) + T(a) + n where a>= 1 is
a constant, by using iteration to generate a guess and then using substitution
to verify it. Show all work.
T(n)= T(n-a) + T(a) + n where a>=1
T(n) = T(n-a) + theta(n)
Each iteration adds O(n) and there are n/a iterations

T(n) = n/a O(n) = O(n^2)

We can work out the iteration

T(n) = T(n-a) + T(a) + n
     = T(n-a-a) + T(a) + n-a + T(a) + n
     = T(n-2a) + 2T(a) + 2n-a
     = T(n-a-2a) + T(a) + n-2a + 2T(a) + 2n-a
     = T(n-3a) + 3T(a) + 3n-a

     The ith iteration adds n, adds T(a) and subtracts i*a

     = T(n-ia) + iT(a) + in-a (sum j=1 to i-a) 


     The argument T is less than the constant a when i= |_n/a_|

     Ignoring the floor,

     T(n) = theta(1) + n/a*theta(1) + n/a *n-a (sum j=1 to (n/a -1))

          = theta(n^2) 
                               
Substitution Method:
To show that T(n) = O(n^2), we want to show by induction that T(n) <= cn^2
for some c>0. Assume that this true for all arguments less than some n.
Later, make sure to pick initial conditions to cover values at
least up to a.

T(n) = T(n-a) + T(a) + n
     <= c(n-a)^2 + ca^2 + n
     = cn^2 -2cna + 2ca^2 + n
     = cn^2 - (2cna - 2ca^2 -n)
     <= cn^2 if 2cna - 2ca^2 -n >= 0

     2cna-2ca^2-n >=0 ==> c(2na -2a^2) >=n==> n/2na-2a^2 = 1/2a - (2a^2)/n
     For n>2a, the last expression is <= 1/a, since a>=1, any c>=1
     works. Pick c large enough to satisfy initial conditions 
     i.e., large enough so that T(n)