Multiple choice

Given numbers 1, 2, 3, 4, 5, 6…. N. Inorder to insert a random permutation of the numbers in binary search tree, what is the average running time?

  1. O(logn)

  2. O(nlogn)

  3. O(n2)

  4. O(n)

  5. O(1)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

 This is correct,  since there are n! permutation. Taking the average of the entire time taken to insert any of the permutations would lead to a complexity of O(nlogn).

Keep practicing — related questions