19. Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
(A) O(l)
(B) O(log n)
(C) O(n)
(D) O(n log n)
Ans: (C)
Explanation :
For a highly balanced binary tree, the number of comparisons it would take to insert a number would be log(n), because we need to compare at each level and height of such tree would be log n (because nodes gets divided into 2 at each step).
But for a skewed tree this is not true. For the worst case assume, a Right Most Tree. The height of such tree would be N, basically because at each step the nodes do not get divided but would be chained. To insert a number, in the worst case, you have to compare with each and every node in the tree. So, the number of comparisons needed would be n.
That means the complexity would be O(n).
Advise :
The best way to answer these questions is to practice writing code for the basic operation of trees i.e., insertion, deletion, addition of elements, height of the tree, in/post/pre order traversals, How to make a balanced tree etc. Write pseudo code for them at the least and and answer how much complexity is this algorithm.
Remember, there is no easy way or short cut for these.
Concepts to Revise :
Trees
Binary Search Trees
Tree basic operation algorithms
Balanced Trees
Complexities
References :
(A) O(l)
(B) O(log n)
(C) O(n)
(D) O(n log n)
Ans: (C)
Explanation :
For a highly balanced binary tree, the number of comparisons it would take to insert a number would be log(n), because we need to compare at each level and height of such tree would be log n (because nodes gets divided into 2 at each step).
But for a skewed tree this is not true. For the worst case assume, a Right Most Tree. The height of such tree would be N, basically because at each step the nodes do not get divided but would be chained. To insert a number, in the worst case, you have to compare with each and every node in the tree. So, the number of comparisons needed would be n.
That means the complexity would be O(n).
Advise :
The best way to answer these questions is to practice writing code for the basic operation of trees i.e., insertion, deletion, addition of elements, height of the tree, in/post/pre order traversals, How to make a balanced tree etc. Write pseudo code for them at the least and and answer how much complexity is this algorithm.
Remember, there is no easy way or short cut for these.
Concepts to Revise :
Trees
Binary Search Trees
Tree basic operation algorithms
Balanced Trees
Complexities
References :
No comments:
Post a Comment