Time Complexity of Binary Search Tree

Posted 27 November 2017 - 04:06 PM

Hi!

I've been doing research into best/average/worst case performance. I'm have just started understanding Big-O notation.
I was under the impression that the worst case performance of a Binary Search Tree would be be o(n) if the data set is ordered, and thus the efficiency would be the same as a Linked List. This makes sense to me!

I was under the impression that that the best case would be O(Log N) due to the binary aspect of the data structure. Would this be the best case or average case? On Wikipedia, it says that deletion, search and addition on average are O(Log N), so what would be the best case? I have done lots of research online, different websites say conflicting things. Some blog points said that the best case would be O(1). My understanding of O(1) describes an algorithm that will always execute in the same time (space) regardless of the size of the data set. So I'm struggling to understand how this can be the best case Time Complexity for Binary Search tree. I would appreciate some insight.

Many Thanks!

Is This A Good Question/Topic? 0

Replies To: Time Complexity of Binary Search Tree

#2 macosxnerd101 • • Games, Graphs, and Auctions
• Reputation: 12607
• Posts: 45,747
• Joined: 27-December 08

Re: Time Complexity of Binary Search Tree

Posted 27 November 2017 - 04:22 PM

Moved to Computer Science.

Quote

I was under the impression that the worst case performance of a Binary Search Tree would be be o(n) if the data set is ordered, and thus the efficiency would be the same as a Linked List. This makes sense to me!

Performance for what operation(s)? This needs to be specified. Also note that Big-O is very different from little-oh. Suppose an algorithm runs in time T(n). We say that T(n) is O(n) if there exist constants c, N such that T(n) <= cn for all n >= N. In limit notation, we are saying that:
```lim(n->infinity) T(n)/n < infinity

```

To contrast, if T(n) is o(n), then we are saying that:
```lim(n->infinity) T(n)/n = 0

```

That is, T(n) grows strictly slower than n. The function T(n) = log(n) is o(n), while the function T(n) is O(n) but not o(n).

Quote

My understanding of O(1) describes an algorithm that will always execute in the same time (space) regardless of the size of the data set.

This is a correct interpretation for worst-case analysis. For best-case analysis, O(1) is correct. Consider an empty BST. How many steps does it take to insert an element?

Now suppose we have a BST T, and are performing a search. If the element we are looking for is the root, then search only takes O(1) time. This is the best case, not the worst or average case.

Re: Time Complexity of Binary Search Tree

Posted 28 November 2017 - 03:54 AM

Thanks for getting back to me!

Sorry, I should have been more clear. When I meant performance, I meant for search, add and remove operations in a Binary Search Tree. For search, remove and add operations, then yes the worst case performance would be O(n), in the case that the Binary Tree is like a Linked List.

On average the performance for search, add and remove operations will be O(Log n) due to the nature of the halving at each step.

Many online sources still state that the best case is also O(Log n), but in fact it should be o(1) correct?

#4 macosxnerd101 • • Games, Graphs, and Auctions
• Reputation: 12607
• Posts: 45,747
• Joined: 27-December 08

Re: Time Complexity of Binary Search Tree

Posted 28 November 2017 - 05:29 AM

That is correct.

Re: Time Complexity of Binary Search Tree

Posted 28 November 2017 - 06:18 AM

Cheers!

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }
{"ft_lang_label":"__label__en","ft_lang_prob":0.92550564,"math_prob":0.81042224,"size":4816,"snap":"2019-26-2019-30","text_gpt3_token_len":1192,"char_repetition_ratio":0.12759767,"word_repetition_ratio":0.7222222,"special_character_ratio":0.25664452,"punctuation_ratio":0.11048159,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9715307,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-06-25T05:46:19Z\",\"WARC-Record-ID\":\"<urn:uuid:30c9b729-1e64-478b-91f9-f6f89217ac4c>\",\"Content-Length\":\"144807\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:15c2f795-32c1-42a6-98ac-859458da2306>\",\"WARC-Concurrent-To\":\"<urn:uuid:7e8588e9-5f15-4444-94b5-9656fb993df9>\",\"WARC-IP-Address\":\"104.25.12.25\",\"WARC-Target-URI\":\"https://www.dreamincode.net/forums/topic/407880-time-complexity-of-binary-search-tree/\",\"WARC-Payload-Digest\":\"sha1:B3VGAVBDJQG4TCUSCC5G54OKOFNMHMPR\",\"WARC-Block-Digest\":\"sha1:IMALVE33WWW3FZJWWXWXUHAYN4CEG535\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-26/CC-MAIN-2019-26_segments_1560627999800.5_warc_CC-MAIN-20190625051950-20190625073950-00318.warc.gz\"}"}