[SOLVED] CSE321 -HW1

Description

 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)

1. c) 𝑛^𝑛 𝜖 𝜃

d)                  𝑂    e) 𝑶

1. f) and (log₂ 𝑛)² are of the same asymptotical order.

• Order the following functions by growth rate and explain your reasoning for each of them.

𝑛², 𝑛³,   𝑛 ^𝑛

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

1. 𝑖
2. i³

2. /𝑖

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.