Please read the assignment
submission rules and the academic dishonesty
page before you start work on this assignment. Failure to comply by
these rules will cost a significant percentage of your assignment grade.
Remember:
1.
Definition: O(g(n))= { f(n): there exist positive constants c and n0
such that 0<=f(n)<=cg(n) for all n>=n0}.
Indicate, for
each pair of expressions(A, B), whether A is the Big
O of B that means A=O(B). Assume that c is a constant and c>1.
a) A=(1+1/n)^n
, B=1
b) A=n! , B=(lg n)!
c) A=n^0.5
, B=n^(sin n)
d) A=n B=(lg
n)^c , for some c>0
e) A=n^lg
c , B=c^lg n
2. Use repeated
substitution to solve the following recurrences (see Example 2.20 on page 91)
Assume that n is a non-negative integer.
a) t(n) = -- 1 if
n=1;
\ 1+2t(n-1) otherwise
b)
/ 1
if n=1;
t(n)
= -- 1
if n=2;
(Fibonacci Array)
\ t(n-1)+t(n-2) otherwise
Tip
for (b):
Consider
g(n)=t(n+1)-t(n)* (1+sqrt(5))/2
So
that for n>1, g(n)= g(n-1)(1-sqrt(5))/2
3. Consider the
following code
public static int f(int
x)
{
int n = 0;
for(int i=0
; i < x ; i++)
{
for(int j=0 ; j < i ; j++ )
{
n++;
}
n++;
}
return n;
}
Of the
following, which best describe the growth of f(x) as a function of x? Justify your answer.
a) Logarithmic
b) Linear
c) Quadratic d) Cubic
e) Exponential
4.
Let
A[1..n] be an array of n distinct numbers. If i<j and A[i]>A[j], then the
pair (i, j) is called an inversion of A.
a) List the inversions of
the array [5, 20, 25, 9, 3]
b) What array with elements
from the set {1,2,…,n} has the most inversions?
Justify your answer.
c) If the length of the input
array is fixed, what is the relationship between the running time of insertion
sort and the number of inversions in the input array? Justify your answer.