Description

Prove using only the definitions of asymptotic notations. (15p)


n2^{n} is in O( 2^{2}^{n} )



n! is in Ω( 2^{n} )



(log n) is in Ө( log _{64} n )


Sort the following functions from slowest to fastest in terms of their growth. Using limit estimation. (10p)
(lgn)^{lgn} , lg(n!) , n , lg(lg(n)) , lg( 2^{n}) , lg(lg( √n))

Solve the following recurrence relation using the substitution method. (15p) T(n) = 2T(n1) + 1 n>1, T(n) = 1 n=1

Explain the running time of f(n) using recurrence relation. (10p)
f(n):
if (n == 1) return 1
else
return f(n1) + f(n1)

What does do UnknownFunction? Analyze the running time of UnknownFunction using proper asymptotic notations. (15p)
UnknownFunction(n):
i = 0
while (n%2 == 0)
n = n/2
i++
return i

Write Insertion sort with pseudocode Explain analyze of your algorithm worstcase, bestcase and averagecase using proper asymptotic notations. (20p)

Calculate the running time of the Test function. Show your calculation in proper asymptotic notations. (20p)
for (int i = 1 ; i < 2n ; i+=4i)
for (int j = n ; j > 0; j–)
if ( i*j == target)
target = checkFunc(n);
else
print();
checkFunc(n){
foo(n);
if (n == 1)
return 1;
else
return checkFunc(n/2);
}
foo(n){
for (int i = 0 ; i < n ; ++i)
print();
}
*Assume that arithmetic operations and print() can be done in constant time.
Note:

Do not email your homework or submit it through moodle.

Your submissions will be handwritten.

You should handover the submissions to theTuğbagül Altan Akın before 12:00 on due date.

Fatma Nur Esirci will score this homework.