CODEWITHSUNDEEP
algorithmruntimebig-o
GothLoli
GothLoli

Reputation: 19

running time of (log base 2 (n) * log base 2 (n))

I know all of basic big o notation stuff

But this one really confuses me... :(

according to Wolfram Alpha

log base 2 (n) * log base 2 (n) is mathematically log^2(n) / log^2(2).

I know big o has to be one of O(1), O(log n), O(n) , O(n log n) ... exponential .. factorial.....

however, I don't know in where log base 2 (n) * log base 2 (n) fits

if I visualize with code like

for ( int x = 1; x < n; x *= 2)
{
    for ( int y = 1; x < m; y *= 2)
    {}
}

it looks like O(log n) Is my guess right?

Upvotes: 0

Views: 7720

Answers (3)

WKara
WKara

Reputation: 109

Try not get confused by (log2 (n)) with (log2 (n)).

(log2(n)) increases by log squared which has a greater time complexity than (log2 (n)).

As I am sure you are aware that in Big O we remove the constants and operators from the equation which causes a time complexity of (log2 (n)) * (log2 (n)) to become O(log (n)) running at a logarithmic time complexity.

Upvotes: 0

Lee.O.
Lee.O.

Reputation: 73

The time complexity is O(log(n) * log (n)) (or you can write O(log^2(n)) ).

The complexity can not be simplified to O(log(n)) similarly to how O(n*n) can not be simplified to O(n). Terms are dropped in complexity calculations, when you have a constant, for example O(4n) becomes O(n), or when you have something like O(n) + O(log(n)) you can drop the latter term, because when n gets very large (goes to positive infinity) then the quotient between the expression O(n) + O(log(n)) and the expression O(n) goes to 1, so that we only keep the O(n) part.

Upvotes: 1

Kaleb Barrett
Kaleb Barrett

Reputation: 1594

You're understanding of Big-O notation is too rigid, there are not some limited set of Big-O functions. The complexity of that snippet would be O(log^2(n)).

Look at the Big-O for this algorithm to solve the travelling salesman problem.

You could say that this might be in the class O(log(n)). But if there is a more precisely known bound, use it if it gives you more information. In this case I think it does.

Upvotes: 1

Related Questions