Question

How do you know an equation has a log (n) algorithm performance? I can't seem to understand how you know it is log(n) compute time

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

Let us take the very basic case.

For example equation is

T(n)=T(n/2)+1

So, basically it can be rewritten as

T(n)=T(n/2^2)+1+1

...

..

T(n)=T(n/2^k)+1*k

So, since the base case is T(1)

n should be 2^k

So,

Take logs on both sides

2^k=n

k=log2(n)

So,

T(n)=T(1)+log2(n)

And since the T(1) is constant and higher term in power of n is log2(n)

So, it is O(log(n))

Kindly revert for any queries

Thanks.