+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
edited | 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 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)