1) For each of the following statements, specify whether it is true or not, and prove your claim. Use the definition of asymptotic notations.
a) log2 2 +1 = Ο( )
b) √ ( + 1) = Ω( )
c) −1= ( )
2) Order the following functions by growth rate and explain your reasoning for each of them. Use the limit method.
2, 3 , 2 log , √ , log , 10 , 2 , 8log2
3) What is the time complexity of the following programs? Use most appropriate asymptotic notation. Explain by giving details.
a)
int p_1 ( int my_array[]){
for(int i=0; i<=n; i++){
if(i%2==0){
count++;
} else{
i=(i-1);
}
}
}
b)
int p_2 (int my_array[]){
first_element = my_array[0];
second_element = my_array[0];
for(int i=0; i<sizeofArray; i++){
if(my_array[i]<first_element){
second_element=first_element;
first_element=my_array[i];
}else if(my_array[i]<second_element){
if(my_array[i]!= first_element){
second_element= my_array[i];
}
}
}
c)
int p_3 (int array[]) {
return array[0] * array[2];
}
d)
int p_4(int array[], int n) {
Int sum = 0
for (int i = 0; i < n; i=i+5)
sum += array[i] * array[i];
return sum;
}
e)
void p_5 (int array[], int n){
for (int i = 0; i < n; i++)
for (int j = 1; j < i; j=j*2)
printf(“%d”, array[i] * array[j]);
}
f)
int p_6(int array[], int n) {
If (p_4(array, n)) > 1000)
p_5(array, n)
else printf(“%d”, p_3(array) * p_4(array, n))
}
g)
int p_7( int n ){
int i = n;
while (i > 0) {
for (int j = 0; j < n; j++)
System.out.println("*");
i = i / 2;
}
}
h)
int p_8( int n ){
while (n > 0) {
for (int j = 0; j < n; j++)
System.out.println("*");
n = n / 2;
}
}
i)
int p_9(n){
if (n = 0)
return 1
else
return n * p_9(n-1)
}
j)
int p_10 (int [ ], int ) {
if ( == 1)
return;
p_10 ( , − 1);
= −1;
while ( > 0 and [ ] < [ − 1]) {
SWAP( [ ], [ − 1]);
= −1;
}
}
4)
a) Explain what is wrong with the following statement. “The running time of algorithm A is at least O(n2 )”.
b) Prove that clause true or false? Use the definition of asymptotic notations.
I. 2 +1 = Θ(2n )
II. 22 = Θ(2n )
III. Let f(n)=O( 2) and g(n)= Θ( 2 ). Prove or disprove that: f(n) * g(n) = Θ( 4 )
5 ) Solve the following recurrence relations. Express the result in most appropriate asymptotic notation. Show details of your work.
a) T(n) = 2T(n/2) + n, T(1) = 1
b) T(n) = 2T(n − 1) + 1, T(0)=0
6) In an array of numbers (positive or negative), find pairs of numbers with the given sum. Design an iterative algorithm for the problem. Test the algorithm with different size arrays and record the running time. Calculate the resulting time complexity. Compare and interpret the test result with your theoretical result.
7) Write a recursive algorithm for the problem in 6 and calculate its time complexity. Write a recurrence relation and solve it.
