CSE 321-Introduction to Algorithms
Homework 1
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.
