Prove using only the definitions of asymptotic notations. (15p)
n2n is in O( 22n )
n! is in Ω( 2n )
(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( 2n) , lg(lg( √n))
Solve the following recurrence relation using the substitution method. (15p) T(n) = 2T(n-1) + 1 n1, 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(n-1) + f(n-1)
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 worst-case, best-case and average-case using proper asymptotic notations. (20p)
Calculate the running time of the Test function. Show your calculation in proper asymptotic notations. (20p)
Test(n):
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.
