Question

  
1)T(n) = 27 T (n/3) + n3

2)Calculate the running time for the following code fragment.

Algorithm test

int counter, i, j;

counter := 0;

for (i:= 1; i < n; i*=2)

{

for (j:= 0; j < i; j++)

{

counter := counter +1

}

}

3)Let f(n) = 2lg 8n + 3 be a function.

Answer 1

1)


2)
let's go through each iteration of the outer loop

i = n
    inner loop iterates n times
i = n/2
    inner loop iterates n/2 times
i = n/4
    inner loop iterates n/4 times
i = n/8
    inner loop iterates n/8 times
i = n/16
    inner loop iterates n/16 times
...
i = 1
    inner loop iterates 1 time

total number of iterations/operations = n + n/2 + n/4 + ... + 1
= n(1 + 1/2 + 1/4 + 1/8 + ...)
we know that 1 + 1/2 + 1/4 + 1/8 + ... <= 2
= n(1 + 1/2 + 1/4 + 1/8 + ...)
<= 2n
so, T(n) = O(n)
Answer: O(n)

3)
f(n) = 2lg 8n + 3
f(n) = O(log n)