How O(log n) is better than O(n) time complexity in DSA?

In Data structure and algorithms we heard a lot that O(log n) is better than O(n) time complexity. 

Today we will prove it with examples.

In mathematics log has base 10 where computer science has a binary system. So, the log base is 2 in computer science.

Let’s prove how logarithmic time complexity is better than linear time.

log(n) = log₂(n)

If log_b(n) = y               where b^y = n;

Example,

log(16) = 4                because 2⁴ = 16
log(n) = y  means  2^y = n

When n increases by double y just need to increase by 1. 

Here are some examples,

    2⁴ = 16

    2⁵ = 32

    2⁶ = 64

So, where we need 64 iterations with O(n) time complexity, we can solve it by just 6 iterations with O(log n) time complexity.

Hence O(log n) is better than linear time complexity O(n).

Although sometimes it is not possible to solve the problem in O(log n) time then O(n) can be the next best time complexity.