Started on Sunday, 20 March 2022, 8:50 AM
State Finished
Completed on Sunday, 20 March 2022, 9:04 AM
Time taken 14 mins 2 secs
Grade 8.00 out of 10.00 (80%)
Question 1
Correct
Mark 1.00 out of 1.00
You can prove that 5n2 + 2n is not O(n) by -------------.
Select one:
a. contradiction
b. direct proof
c. induction
The correct answer is: contradiction
Question 2
Correct
Mark 1.00 out of 1.00
The purpose of asymptotic notation is to suppress ------------- which are too system dependent.
Select one:
a. higher-order terms
b. constant factors
c. lower-order terms
d. logarithmic terms
The correct answer is: constant factors
Question 3
Correct
Mark 1.00 out of 1.00
In mathematical induction, ---------- proves that if the statement is true for the nth iteration, then it is also true for (n+1)th iteration.
Select one:
a. Iterative step
b. Inductive step
c. Base step
d. Initial step
The correct answer is: Inductive step
Question 4
Correct
Mark 1.00 out of 1.00
The runtime of insertion sort is ---------------.
Select one:
a. O(n2)
b. O(log n)
c. O(n log n)
d. O(n)
The correct answer is: O(n2)
Question 5
Incorrect
Mark 0.00 out of 1.00
The purpose of asymptotic notation is to suppress ------------- and ------------.
Select one:
a. constant factors, lower-order terms
b. logarithmic terms, higher-order terms
c. logarithmic terms, lower-order terms
d. constant factors, higher-order terms
The correct answer is: constant factors, lower-order terms
Question 6
Correct
Mark 1.00 out of 1.00
Arrange the following functions in order of increasing growth rate: !n, n2, n, 2n
Select one:
a. n, n2 , 2n, !n
b. n2 , n, 2n, !n
c. n, n2, !n , 2n
d. n, 2n, n2, !n
The correct answer is: n, n2 , 2n, !n
Question 7
Incorrect
Mark 0.00 out of 1.00
When Karatsuba algorithm is used to multiply two n-digit integers, it is of ------------ complexity.
Select one:
a. n1.6
b. n3
c. n log n
d. n2
The correct answer is: n1.6
Question 8
Correct
Mark 1.00 out of 1.00
The following graph represents ------.
Select one:
a. T(n) = Ω(f(n))
b. T(n) = Θ(f(n))
c. T(n) = O(f(n))
The correct answer is: T(n) = O(f(n))
Question 9
Correct
Mark 1.00 out of 1.00
Suppose that g(n) > 0 for all integers n. Then is f (n) = O(g(n)) equivalent to the following simpler definition that avoids n0?
Select one:
a. False
b. True
The correct answer is: True
Question 10
Correct
Mark 1.00 out of 1.00
Suppose that f (n) = O(g(n)). Which of the following is implied by this fact?
Select one:
a. Both g(n) = Ω(f(n)) and g(n) = O(f(n)) are true
b. Neither g(n) = Ω(f(n)) nor g(n) = O(f(n)) is true
c. g(n) = O(f(n))
d. g(n) = Ω(f(n))
The correct answer is: g(n) = Ω(f(n))
