Is the complexity of 3 logn and 2logn same?

Question

DOes it have same complexity since they vary by constant multiplier, or should it be made n^3 and n^2 and be compared?

Answer 1

For 'BigOh' notation, the constant multiplier really doesn't matter. All that it does is, it gives the order of the running time complexity. You can consider this small example: Say you have 3 * 100 = 300 apples and 2 * 100 = 200 apples. Surely, 300 != 200, but the order of both are same, that is in order of hundreds.

So by the same means, 3(log n) != 2(log n), but both 3(log n) and 2(log n) are in the order of log n, that is O(log n).

Answer 2

Yes. Multiplying by a constant doesn't matter. The are both just O(log n).

In fact, this is part of the definition of big-o notation. If a function may be bounded by a polynomial in n, then as n tends to infinity, you may disregard lower-order terms of the polynomial.