The Gateway to Computer Science Excellence
+1 vote
72 views

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 by Veteran (74.6k points)
edited by | 72 views
0
why O(n)

why not O(logn)  ???
0
@SKP

Because it says in question "  tightest upper bound " ..

inserting an element into a binary search tree of n nodes takes O( logn) as there are log n levels ( suppose tree is balanced ) and inserting  cost at every level is O(1) so total cost =O(logn)

But in worst case it can take O(n)
0
Sorry Bikram but I didn't got your worst case time.
+2

@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) 

0

yeah, now I got it right O(n)

thanks @Bikram 

1 Answer

+1 vote

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

by Veteran (74.6k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,336 answers
198,447 comments
105,203 users