COS

COS2611
Past exam Q & A

, MCQ
October 2017
1. Which of the following functions is ordered by growth rate from largest to smallest?
ORDERS OF MAGNITUDE (small to large): 1, N, log , Nlog , N , N , 2 , N!
a. Nlog , 2 , N , 2
b. 2 , Nlog , N , 2
c. 2 , N , Nlog , 2
d. 2 , 2 , N , Nlog
e. 2 , N , 2 , Nlog
2. What is the running time of the following code fragment?
for (int i = 0; i < 5n; i++) 1; 5N + 1; 5N = 10N + 2
sum++; O(N)
a. O(1)
b. O(N)
c. O(log )
d. O(Nlog )
e. O(N )

Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2) 1; 10001; 10000/2 = O(1)
2. for (int k = 1; k <= n; k++) 1; N + 1; N = 2N + 2
3. sum++; (2N + 2) ∗ 1

4. for (int p = n; p > 1; p /= 2) 1; N + 1; log = N + 2 + log
5. for (int q = 0; q < 500; q++) 1; 501; 500 = O(1)
6. sum--; (log + N + 2) ∗ 1
3. How many times is statement 3 executed?
a. O(N)
b. O(N )
c. O(N )
d. O(Nlog )
e. O(log )
4. How many times is statement 6 executed?
a. O(N)
b. O(N )
c. O(N )
d. O(log )
e. O(Nlog )
5. What is running time of the entire code fragment?
a. O(N)
b. O(N )
c. O(N )
d. O(log )
e. O(Nlog )
6. An algorithm takes 5 seconds for an input size of 10. How long will it take for an input size of 20 if the
running time is O(N )?
∗
5sec = 10 ; 𝑥sec = 20 𝑥sec =
a. 2s
b. 4s
c. 30s
d. 40s
e. None of the above
7. An algorithm takes 5 seconds for an input size of 500. How large a problem can be solved in 50 seconds
if the running time is linear O(N)?
∗
5sec = 500; 50sec = 𝑥 𝑥=
a. 50
b. 500
c. 5000