How binary search has O(log(n)) complexity?? | Sololearn: Learn to code for FREE!

How binary search has O(log(n)) complexity??

26th Jun 2020, 12:17 PM
Wasi - avatar
3 Respostas
+ 3
In computer science we usually take log (base 2) as default. If n=8 then (log(base 2) n) would be 3, which is the height. The 8 will split into 4 then 4 into 2 then 2 into 1. See 3 times, so the height is 3.
26th Jun 2020, 12:25 PM
Blue!! - avatar
+ 2
Binary tree is an interesting data structure with many implementations. Look at this lesson to get a quick idea Binary tree is another common implementation of the binary tree, which is described here "" As the keys are stored in a particular order, the principle of binary search can be used for lookup. We start from the root and compare the key. if the root has the key, it is returned as the result. If the key is greater than the root, the right subtree is recursively checked. If the key is less than the root, the left subtree is recursively checked. The recursion continues until the key is found. "" And thus it ensures the lookup to be O(log n) - Try to understand with the diagram I think those 2 resources are enough to get an idea but feel free to ask any question :)
26th Jun 2020, 2:06 PM
Seniru - avatar
26th Jun 2020, 12:41 PM
Wasi - avatar