It's diffcult for me to understand logarithmic complexity of algorithm.
For example
for(int j=1; j<=n; j*=2){
...
}
Its complexity is O(log2N)
So what if it is j*=3? The complexity will then be O(log3N)?
-
The last slide of this document explains the general case of logarithmic loops.Mohamed Ennahdi El Idrissi– Mohamed Ennahdi El Idrissi2014-04-11 01:34:40 +00:00Commented Apr 11, 2014 at 1:34
Add a comment
|
2 Answers
You could say yes as long as the loop body is O(1).
However, note that log3N = log2N / log23, so it is also O(log2N), since the constant factor does not matter.
Also note it is apparent from this argument, for any fixed constant k, O(logkN) is also O(log2N), since you could substitute 3 with k.
3 Comments
Patricia Shanahan
That is why logarithmic complexity is usually stated as just "log N" without specifying the base.
zw324
@PatriciaShanahan Mmm, I always thought of plain
log as log base 2, but your way of looking at that make sense too.
Ayman
In Big O notation what matters is not Log2 or Log3, what matters is how does the algorithm complexity grow with respect to the input size. Constant time, Log, Linear and Exp are the common ones.
Basicly, yes. Let's assume that your for loop looks like this:
for (int j = 1; j < n; j *= a) {...}
where a is some const.
If the for loop executes k times, then in the last iteration, j will be equal to ak. And since N = O(j) and j = O(ak), N = O(ak). It follows that k = O(logaN). Once again, for loop executes k times, so time complexity of this algorithm is O(k) = O(logaN).
