O (log (n)) * O (log (n)) in complexity theory

Tackled with some kind of silly question on complexity.

I have a loop that runs time O(lg(n)). I have another loop inside that is also equal O(lg(n)), so all complexity O(lg(n)) * O(lg(n))or O (lg (n) 2 ) . May I say that the final O is equal O(lg(n)), since since n is a power of 2, then

O (lg (n)) * O (lg (n)) = O (lg (n 2 )) = O (2lg (n)) = O (lg (n)))

or cannot it be used in this way?

+4
source share
1 answer

, ! :

O (lg (n)) * O (lg (n)) = O (lg (n 2))

. . O (lg (n) 2)

+7

All Articles