CMPSC 465 Data Structures & Algorithms
Fall 2021 and Quiz 1
Recitation Section: Monday, Aug 30, 2021
Student Name: PSU Email ID:
1. (2 pts.) Worst case time complexity of insertion
sort where position of the data to be inserted is cal-
culated using binary search is:
(a) O(n)
(b) O(n2)
(c) O(n · logn)
(d) O(n · (logn)2)
Answer (b) Time required to swap elements in the
correct position is still O(n)
2. (2 pts.) While performing insertion sort on the ar-
ray {7,5,4,2,3,1}, which of the following is NOT
a transition state of the array:
(a) 4 5 7 2 3 1
(b) 7 5 4 2 1 3
(c) 2 3 4 5 7 1
(d) 5 7 4 2 3 1
(e) None of the above
Answer (b) Insertion sort runs from index 1 to n
and sorts the sub array 1 to i before moving to i+1
index
3. (2 pts.) Which of the following is correct:
I 2n+1 = O(2n)
II 22n+1 = O(2n)
(a) I is correct
(b) II is correct
(c) Both I and II are correct
Answer (a) II is incorrect as 22n+1 = 2n+1 · 2n =
2n+1 ·O(2n), doesn’t satisfy the definition of Big-
O as c, the coefficient, is not a constant.
4. (2 pts.) f (n) = 3n2 and g(n) = 2n3. Which of the
following is correct
I f (n) = O(g(n))
II g(n) = O( f (n))
(a) I is correct
(b) II is correct
(c) Both I and II are correct
Answer (a) As n2 < n3 in terms of order of growth 5. (2 pts.) Consider the following algorithm to iden- tify if a given number n is prime. Let T (n) be the number of times the for loop is executed by the program on input n. Which of the following is true: for i := 2 to √ n do if n mod i == 0 then print “Not Prime” return 0 end return 1 end (a) T (n) = O( √ n) and T (n) = Ω( √ n) (b) T (n) = O(n) and T (n) = Ω( √ n) (c) T (n) = O( √ n) and T (n) = Ω(1) (d) T (n) = O(n) and T (n) = Ω(n) Answer (c) Big O notation defines a tight up- per bound and Big Omega notation defines a tight lower bound for an algorithm. The for loop in the question is run maximum √ n times and minimum 1 time. So, the correct option is (c). CMPSC 465, Fall 2021, Quiz 1 1