senshi nakamora - 7 months ago 36

Java 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

Answer

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)

Source (Stackoverflow)