Big O notation in different data structures

Question

I was reading about Big O notation in java , I found the following questions, I don't understand the answers of them.

(a) What is the worst-case asymptotic running-time for the best algorithm for finding something in a dictionary implemented with a sorted array? O(log n)

(b) What is the best-case asymptotic running-time for the best algorithm for finding something in a dictionary implemented with a sorted array? O(1)

(c) What is the worst-case asymptotic running-time for the best algorithm for finding something in a dictionary implemented with a sorted linked list? O(n)

(d) What is the best-case asymptotic running-time for the best algorithm for finding something in a dictionary implemented with a sorted linked list? O(1)

(e) Given a binary search tree, find which value is the minimum value and delete it. O(n)

(f) Given a binary search tree, find which value is the median value, and delete that value. O(n)

Can you explain to me the answers, and what do they mean by that specific algorithm in the first four questions?

Thanks

The answers tell you, in big-O notation, the complexity asked for in the respective questions. — Marko Topolnik, Nov 22 '16 at 15:15
for ex . what do they mean by that specific algorithm in the first four questions? — senshi nakamora, Nov 22 '16 at 15:16
Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — nbokmans, Nov 22 '16 at 15:16
What specific algorithm? Those questions are talking about the theoretical best/worst cases. — azurefrog, Nov 22 '16 at 15:16
I would assume for number one they are referring to [binary search algorith](https://en.wikipedia.org/wiki/Binary_search_algorithm). — James C. Taylor IV, Nov 22 '16 at 15:18
q2 would also be in reference to a Binary Search. If you read the implementation of it, the case where it will be O(1) will be pretty apparent. — James C. Taylor IV, Nov 22 '16 at 15:21
@senshinakamora Stop trying to fish for answers in the comments. You need to take the [Tour](http://stackoverflow.com/tour) and read the documentation in the [Help Center](http://stackoverflow.com/help). In particular, you should read about [how to ask a good question](http://stackoverflow.com/help/how-to-ask) and what sorts of questions are [on topic](http://stackoverflow.com/help/on-topic) here at SO, and then rewrite your question to make it appropriate this site. — azurefrog, Nov 22 '16 at 15:25
q3 and q4 deal are not a specific algorithm, but simply in reference to performing operations on a linked list. See the [link list article](https://en.wikipedia.org/wiki/Linked_list) and check the linked list vs. dynamic arrays section. — James C. Taylor IV, Nov 22 '16 at 15:27
Marko Topolnik iNan João Vilaça azurefrog why it is O(n) in question (e) ? It should be O(nlog(n)) because deleting in a BST costs O(log(n)) ... Am I thinking right? — senshi nakamora, Nov 22 '16 at 15:28
@Carcigenicate why it is O(n) in question (e) ? It should be O(nlog(n)) because deleting in a BST costs O(log(n)) ... Am I thinking right? — senshi nakamora, Nov 22 '16 at 15:33
help me with question e ... thanks ,, I need help ,, help me — senshi nakamora, Nov 22 '16 at 15:38
@senshinakamora Finding the minimum *could* be O(n) in the worst case if the tree resembled a linked list. — Carcigenicate, Nov 22 '16 at 15:48
Guys, this question is not too broad. The asker tries to understand complexities. — Lajos Arpad, Nov 22 '16 at 16:43

score 2 · Accepted Answer · answered Nov 22 '16 at 16:42

Big O is the worst-case scenario. When you want to calculate the big O, you need to assume that everything will be found at the last item, the sky is black, etc.

(a) The best algorithm is binary search, which guesses in the middle of the sorted array and if the needle is larger, then guesses the middle point of the latter elements, otherwise the former elements. This is repeated until the element is found or the subset is trivial. Since you always have two possible decisions, and on each decision the size of the set is halved, the number of steps is repeated the number of times your set can be halved, which is the number which, as a power of 2 would yield the size of the set. This is log(n). The worst-case scenario is that all the steps need to be performed, that is, O(log(n)).

(b) The best case is that the item happens to be exactly at the middle of the set, which happens to be the first guess, therefore the result is O(1).

(c) In a linked list you cannot do a binary search even if it is sorted, since you can only get the next element from a given element. The worst case is that the needle happens to be the very last one. O(n)

(d) The situation is same as above, but the best case is when the very first item happens to be the searched item. O(1)

(e) In a balanced BST the search time would be O(logn) and removal would be O(1). But if we assume the worst, that is, the BST is unbalanced and the root is the maximum, then a search would traverse all items until it reaches the only leaf, the minimum O(n) and removes it O(1).

(f) To find the median in a BST you might need to traverse all nodes, imagine the case when the root has two children and the leftmost child has only right child and the rightmost child has only left child and the tree has a total of two leafs. In this case, the worst case scenario is when you have chosen the wrong direction and traversed the wrong side and then have to traverse to the good direction as well where he very last element is the one you are searching for. O(n)

@senshinakamora, you are welcome. – Lajos Arpad Nov 22 '16 at 17:06 — Lajos Arpad, Nov 22 '16 at 17:06

Big O notation in different data structures

1 Answers1