Solved–Homework 02– Solution

Description

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

1. 1. n2ⁿ is in O( 2²ⁿ )

1. 2. n! is in Ω( 2ⁿ )

1. 3. (log n) is in Ө( log ₆₄ n )

2. 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ⁿ) , lg(lg( √n))

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

3. 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)

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

6. Write Insertion sort with pseudocode Explain analyze of your algorithm worst-case, best-case and average-case using proper asymptotic notations. (20p)

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