1

I see where most readings online derive that the Big-Oh notation of a Binary Search is O(log(n)), but doesn't this assume a balanced tree? What if the tree is completely unbalanced (i.e. similar to a linked list). In this case the height of the tree is not log(n) it is n.

So considering that Big-Oh takes into account the worst case, why isn't the Binary Search O(n)?

2
  • Robert - Thanks for the clarification. These problems can start to become strange when you think about all of the bizarre cases that can be thrown into the mix
    – JBurk94
    Apr 20, 2016 at 3:54
  • 3
    Binary search doesn't usually apply to trees, but to sorted arrays. In a tree it's not under your control which element you pick next.
    – gnasher729
    Apr 20, 2016 at 7:59

2 Answers 2

5

I see where most readings online derive that the Big-Oh notation of a Binary Search is O(log(n)), but doesn't this assume a balanced tree? What if the tree is completely unbalanced (i.e. similar to a linked list). In this case the height of the tree is not log(n) it is n.

Binary Search doesn't assume a tree at all. Binary Search assumes a data structure that is

  • random access (in constant time) and
  • sorted.

An array, a vector, or an ordered hashtable, for example.

What you are probably thinking about is Lookup in a Binary Search Tree.

So considering that Big-Oh takes into account the worst case, why isn't the Binary Search O(n)?

Big-Oh doesn't take anything into account.

Big-Oh describes the growth rate of a function by comparing it to the growth rate of another function. What those functions mean is totally irrelevant to Big-Oh. It could be a function describing the worst-case time complexity of an algorithm. It could be a function describing the best-case time complexity of an algorithm. It could be a function describing the average case time complexity of an algorithm. It could be a function describing the amortized worst-case time complexity of an algorithm. It could be a function describing the worst-case step complexity of an algorithm. It could be a function describing the worst-case space complexity of an algorithm. It could be a function describing the amount of humans in the world as a function of time. It could be a function describing the amount of money a movie makes in relation to its production cost. It could be a function that describes the amount of money a movie makes in relation to the breast size of the female lead character.

Big-Oh doesn't care. Big-Oh simply says: this function grows faster than that other function. (That's a gross simplification I use only for effect!) That's it. How you interpret the function is up to you, it has nothing to do with Big-Oh.

2

Yes, the assumption is that it is a balanced binary tree, or at least one that is randomly loaded. The linked list scenario is only one configuration of many, and your odds of getting it by chance are vanishingly small, unless you sort your nodes first, before inserting them into the tree.

Searches in a balanced binary tree are O(log(n)) in the worst case.

2
  • Strictly speaking, "binary search", is establishing the existence or non-existence of a specific value as a key (frequently assuming the identity key) in an array-like data structure with sorted data.
    – Vatine
    Apr 20, 2016 at 15:49
  • @Vatine: Yes, I assumed that, because he was talking about Binary Trees, that's what he meant. The differences between a binary tree and a binary search, for purposes of this discussion, are almost inconsequential; they're both still O(log(n)), because they both essentially use the same bifurcating mechanism for search. Apr 20, 2016 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.