CODEWITHSUNDEEP
algorithmbig-o
Varun Subramanian
Varun Subramanian

Reputation: 73

Is the complexity of 3 logn and 2logn same?

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

Upvotes: 4

Views: 1641

Answers (4)

Nick Zuber
Nick Zuber

Reputation: 5637

Big O notation is defined by the set of all upper bounded functions.

With that being said, it is also important to note that Big O can be defined mathematically as:

O(g(n)) = {f(n): f(n) < c·g(n), c being some arbitrary constant}

So as you can see, the constant doesn't really matter in Big O; we don't care if there is one that works. So both 3logn and 2logn both can be described as O(logn).

Upvotes: 0

insanegupta
insanegupta

Reputation: 51

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

Upvotes: 5

harry
harry

Reputation: 116

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.

Upvotes: 1

Geewiz
Geewiz

Reputation: 1

Both are equivalent to O(log n). The constant does not alter the complexity.

Upvotes: 0

Related Questions