Homework 02 Solution

$30.00 $24.90

Description

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

    1. n2n is in O( 22n )

    1. n! is in Ω( 2n )

    1. (log n) is in Ө( log 64 n )

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

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

  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)

  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

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

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