CODEWITHSUNDEEP
algorithmcomplexity-theorybig-otime-complexity
Deqing
Deqing

Reputation: 14632

Logarithmic complexity of an algorithm

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)?

Upvotes: 1

Views: 526

Answers (2)

michelangelo
michelangelo

Reputation: 1

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).

Upvotes: 0

zw324
zw324

Reputation: 27200

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.

Upvotes: 7

Related Questions