CSE 321-Introduction to Algorithms Homework 1 solution

Description

1)
For each of the following statements, specify whether it is true or not. Explain your
reasoning for each of them.
a) log2 𝑛
2 + 1 ∈ Ο(𝑛)
b) √𝑛(𝑛 + 1) 𝜖 Ω(𝑛)
c) 𝑛
𝑛−1
𝜖 𝜃(𝑛
𝑛)
d) 𝑂(2
𝑛 + 𝑛
3
) ⊂ 𝑂(4
𝑛
)
e) 𝑶(2 log3 √𝑛
3
) ⊂ 𝑂(3 log2 𝑛
2
)
f) log2 √𝑛 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
, 𝑛
2
log 𝑛, √𝑛, log 𝑛, 10𝑛
, 2
𝑛
, 8
log𝑛

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) ∑ 𝑖
2
log 𝑖
𝑛
𝑖=1
b) ∑ i
n 3
i=1
c) ∑ 1/(2√𝑖)
n
i=1
d) ∑ 1/𝑖
n
i=1
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.