## 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.