in DS edited by
426 views
1 vote
1 vote

Which one of the following is the tightest upper bound that represents the time complexity of inserting an element into a binary search tree of n nodes?

  1. O(1)
  2. O(n log n)
  3. O(n)  
  4. O(log n)
in DS edited by
by
426 views

4 Comments

Sorry Bikram but I didn't got your worst case time.
0
0

@skp

To insert an element, we need to search for its place first.

The search operation may take O(n) for a skewed tree like following.

To insert 60, we will have to traverse all nodes.
        
20
 \
  30
    \
     40
       \
        50                                

after finding 50 from top to bottom we can insert 60 only in this tree .. so worst case time it takes O(n) 

2
2

yeah, now I got it right O(n)

thanks @Bikram 

0
0

1 Answer

1 vote
1 vote

in worst case the tree can grow up to the height of n (skewed tree), therefore tightest upper bound is O(n)

Answer:

Related questions