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
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.
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