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?
source
share