Suppose we need to write an efficient program to store N employee records for ABC Inc where each employee record is identified by unique employee id. Consider the following ways to store the records.

An array list sorted by employee id

A linked list sorted by employee id

A linked list not sorted

A balanced binary search tree with employee id as key

For data structure A -D, what is the average time to insert a new employee record given employee id as a key?

A B C D

O(N) O(N) O(1) O(log N)

O(N) O(log N) O(N) O(1)

O(log N) O(N) O(log N) O(log N)

O(N) O(log N) O(log N) O(1)

O(log N) O(log N) O(1) O(1)