Multiple Choice Questions

1. when f O(g) then this mean

(a) f is growing faster than g (b) f is growing at the same rate as g

(c) f is growing slower than g (d) growth rate is not related to this statement

2. if f(n) = n+1, g(n) = 2n and we prove that f(n) <= g(n) for n>=1 then

(a) f(n) (g) (b)f(n) (g) (c)f(n) O(g) (d)f(n) o(g)

3. Consider the following algorithm

for i = 1 to lg₂ n

k=n

while k>=1 do

-----

k=k/2

end while

end i

The complexity of the above algorithm is

a) (log₂ n²) b) (log₂ n ) c) (n log₂ n) (d) ((log₂ n)² )

4. 2n logn + 2n + 5 is in:

(a) (n²). (b)O (n²). (c) (n³). (d) (n³).

5. The complexity of the following algorithm is

for (i = 0; i < n; i=i*2) {

for (j = 1; j < n; j++) {...}

}

a) (log₂ n²) b) (log₂ n ) c) (n log₂ n) d) ((log₂ n)² )

6. Which of these is the correct theta for 1+2+3+...+n?

(a) (log n) (b) (n) (c) (n log n) (d) (n)

7. if A(n) = n log n +n²+1000 then A(n)

a) (n³) b) (n log n) c) O(n) d) (n²)

8. Consider the following algorithm

For i=1 to n

For j= i to n

For k=1 to 10

x=x+k

End

End

End

The complexity of the above algorithm is

a) (n) b) ( n³ ) c) ( n²) d) (10)

9. What is the worst-case time analysis for the following loop?

while (n > 0) { n = n/10; }

(a) (1) b) (log₁₀ n) c) (n) d) (n)