Introduction to Algorithms
1)
For each of the following statements, specify whether it is true or not. Explain your reasoning for each of them.
a) b)
c) ๐๐ ๐ ๐
d) ๐ e) ๐ถ
f) and (log2 ๐)2 are of the same asymptotical order.
2) Order the following functions by growth rate and explain your reasoning for each of them.
๐2, ๐3, ๐ ๐
3) What is the time complexity of the following programs? Explain by giving details. a) void f( int my_array[]){
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];
}
}
}
}
b)
void f(int n){ int count=0;
for(int i=2;i<=n;i++){
if(i%2==0){
count++;
}
else{
i=(i-1)i;
}
}
}
4 ) Find the complexity classes of the following functions using the integration method.
a) ๐
b) i3
c)
d) /๐
5) Find the best case and worst case complexities of linear search with repeated elements, that is, the elements in the list need not be distinct. Show your analysis.
