CS 1332 Big O Exam 2 Questions With Correct Answers.

CS 1332 Big O Exam 2 Questions With
Correct Answers

What |is |the |average |case |of |adding |to |a |BST? |- |CORRECT |ANSWER✔✔-O(log(n))



What |is |the |worst |case |of |adding |to |a |BST? |Why? |- |CORRECT |ANSWER✔✔-O(n) |because |of |
the |degenerate |(linked |list) |case



What |is |the |average |case |of |removing |from |a |BST? |- |CORRECT |ANSWER✔✔-O(log(n))



What |is |the |worst |case |of |removing |from |a |BST? |Why? |- |CORRECT |ANSWER✔✔-O(n) |because |
of |the |degenerate |(linked |list) |case



What |is |the |average |case |of |searching |for |a |value |in |a |BST? |- |CORRECT |ANSWER✔✔-O(log(n))



What |is |the |worst |case |of |searching |for |a |value |in |a |BST? |Why? |- |CORRECT |ANSWER✔✔-O(n) |
because |of |the |degenerate |(linked |list) |case



What |is |the |average/worst |case |of |determining |the |height |of |a |BST? |- |CORRECT |ANSWER✔✔-
O(n)



What |is |the |average |(amortized) |case |of |adding |to |a |heap? |- |CORRECT |ANSWER✔✔-O(log(n))



What |is |the |worst |case |of |adding |to |a |heap? |Why? |- |CORRECT |ANSWER✔✔-O(n) |because |of |
the |resize

, What |is |the |average/worst |case |of |removing |from |a |heap? |- |CORRECT |ANSWER✔✔-O(log(n))



What |is |the |average/worst |case |of |accessing |the |min/max |element |in |a |heap? |- |CORRECT |
ANSWER✔✔-O(1)



What |is |the |average/worst |case |of |the |upheap/downheap |operation? |- |CORRECT |
ANSWER✔✔-O(log(n))



What |is |the |average/worst |case |of |searching |for |a |value |in |a |heap? |- |CORRECT |ANSWER✔✔-
O(n)



What |is |the |average/worst |case |for |the |buildHeap |operation? |- |CORRECT |ANSWER✔✔-O(n)



What |is |the |average/worst |case |for |building |a |heap |without |the |buildHeap |algorithm? |- |
CORRECT |ANSWER✔✔-O(n |log(n))



What |is |the |average |case |for |adding |to |a |hashMap |with |a |very |bad |hashing |function? |- |
CORRECT |ANSWER✔✔-O(n)



What |is |the |worst |case |for |adding |to |a |probing |hashMap |with |any |hashing |function? |Why? |- |
CORRECT |ANSWER✔✔-O(n^2) |because |of |the |resize



What |is |the |average/worst |case |for |removing |from |a |hashMap |with |a |very |bad |hashing |
function? |- |CORRECT |ANSWER✔✔-O(n)



What |is |the |average/worst |case |for |searching |for |a |value |in |a |hashMap |with |a |very |bad |
hashing |function? |- |CORRECT |ANSWER✔✔-O(n)