Question 4

Which of the following statements are true about the running time of binary search trees? Assume that when we use big-O notation we mean the tightest big-O bound. Select all that apply.

1 point

The tightest possible worst case time to find an element in an arbitrary BST is O(n)

The tightest possible worst case time to find an element in an arbitrary BST is O(log(n))

The tightest possible worst case time to find an element in a balanced BST is O(log(n))

Inserting sorted data into an unbalanced BST leads to the worst case BST structure (i.e. a structure where finding an element will take the longest).

The tightest possible worst case time to find an element in a balanced BST is O(n)