COS2611 EXAM ACTUAL QUESTIONS AND ANSWERS
WITH COMPLETE VERIFIED 100% SOLUTIONS GRADED
A++ GUARANTEED PASS
Which of the following functions is ordered by growth rate from largest to smallest?
ORDERS OF MAGNITUDE (small to large):
1, N, logN, NlogN, N2, N3, 2N, N!
2N, N3, NlogN, 24
What is the running time of the following code fragment?
for (int i = 0; i < 5n; i++)
sum++;
calculation:
1; 5N + 1; 5N = 10N + 2 O(N)
O(N)
Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2)
2. for (int k = 1; k <= n; k++)
,3. sum++;
4. for (int p = n; p > 1; p /= 2)
5. for (int q = 0; q < 500; q++)
6. sum--;
calculation:
1; 10001; 10000/2 = O(1)
1; N + 1; N = 2N + 2
(2N + 2) ∗ 1
1; N + 1; logN = N + 2 + logN
1; 501; 500 = O(1)
(logN + N + 2) ∗ 1
How many times is statement 3 executed?
O(N)
Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2)
2. for (int k = 1; k <= n; k++)
3. sum++;
4. for (int p = n; p > 1; p /= 2)
5. for (int q = 0; q < 500; q++)
,6. sum--;
calculation:
1; 10001; 10000/2 = O(1)
1; N + 1; N = 2N + 2
(2N + 2) ∗ 1
1; N + 1; logN = N + 2 + logN
1; 501; 500 = O(1)
(logN + N + 2) ∗ 1
How many times is statement 6 executed?
O(logN)
Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2)
2. for (int k = 1; k <= n; k++)
3. sum++;
4. for (int p = n; p > 1; p /= 2)
5. for (int q = 0; q < 500; q++)
6. sum--;
calculation:
, 1; 10001; 10000/2 = O(1)
1; N + 1; N = 2N + 2
(2N + 2) ∗ 1
1; N + 1; logN = N + 2 + logN
1; 501; 500 = O(1)
(logN + N + 2) ∗ 1
What is running time of the entire code fragment?
O(N2)
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(N3)?
calculation: 5sec*20 3
5sec = 10 3; xsec = 20 3 xsec = ------------
10 3
40s
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)?
calculation: 50sec*500
5sec = 500; 50sec = x x = ------------
5sec
WITH COMPLETE VERIFIED 100% SOLUTIONS GRADED
A++ GUARANTEED PASS
Which of the following functions is ordered by growth rate from largest to smallest?
ORDERS OF MAGNITUDE (small to large):
1, N, logN, NlogN, N2, N3, 2N, N!
2N, N3, NlogN, 24
What is the running time of the following code fragment?
for (int i = 0; i < 5n; i++)
sum++;
calculation:
1; 5N + 1; 5N = 10N + 2 O(N)
O(N)
Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2)
2. for (int k = 1; k <= n; k++)
,3. sum++;
4. for (int p = n; p > 1; p /= 2)
5. for (int q = 0; q < 500; q++)
6. sum--;
calculation:
1; 10001; 10000/2 = O(1)
1; N + 1; N = 2N + 2
(2N + 2) ∗ 1
1; N + 1; logN = N + 2 + logN
1; 501; 500 = O(1)
(logN + N + 2) ∗ 1
How many times is statement 3 executed?
O(N)
Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2)
2. for (int k = 1; k <= n; k++)
3. sum++;
4. for (int p = n; p > 1; p /= 2)
5. for (int q = 0; q < 500; q++)
,6. sum--;
calculation:
1; 10001; 10000/2 = O(1)
1; N + 1; N = 2N + 2
(2N + 2) ∗ 1
1; N + 1; logN = N + 2 + logN
1; 501; 500 = O(1)
(logN + N + 2) ∗ 1
How many times is statement 6 executed?
O(logN)
Questions 3, 4 and 5 refer to the following code fragment:
1. for (int j = 1; j <= 10000; j *= 2)
2. for (int k = 1; k <= n; k++)
3. sum++;
4. for (int p = n; p > 1; p /= 2)
5. for (int q = 0; q < 500; q++)
6. sum--;
calculation:
, 1; 10001; 10000/2 = O(1)
1; N + 1; N = 2N + 2
(2N + 2) ∗ 1
1; N + 1; logN = N + 2 + logN
1; 501; 500 = O(1)
(logN + N + 2) ∗ 1
What is running time of the entire code fragment?
O(N2)
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(N3)?
calculation: 5sec*20 3
5sec = 10 3; xsec = 20 3 xsec = ------------
10 3
40s
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)?
calculation: 50sec*500
5sec = 500; 50sec = x x = ------------
5sec
