CODEWITHSUNDEEP
algorithmbig-o
jAckOdE
jAckOdE

Reputation: 2510

What is better BigO log(m*n) or (m+n)?

With m and n being the two dimensions of a 2D matrix, which search algorithms with givens Big-O are considered faster:

Upvotes: 0

Views: 2116

Answers (4)

twalberg
twalberg

Reputation: 62469

Neither one is "best" outside the context of a specific application. Remember that O(f(x)) means that the time an algorithm takes to process an input of size x is proportional to f(x), with no indication of what that proportion is. If you have one algorithm that is O(n) (i.e. linear), but there is a constant multiplicative factor of, say 10^4, and a second algorithm that is O(n^2), but only has a multiplicative factor of 1, then the second algorithm is going to be better for problem sizes of up to 10^4. If your actual problem domain is guaranteed to never have inputs with sizes exceeding 10^2, there is no reason whatsoever that you would pick the first algorithm. This is admittedly an extreme example, but the point is that you need to know your problem domain and the inputs you expect to have to handle, as well as the different algorithms you are evaluating and the associated costs in order to pick the best algorithm for your program. There are a great many real-world situations, where picking the mathematically most efficient (for extremely large-scale problems) algorithm is not the right choice, and can actually cause performance issues, because your inputs are never large enough to realize the savings in efficiency that is theoretically possible.

In your specific case, the O(log(m*n)) is definitely the most efficient as the size of your problems grow, but if you are never operating in the realm of larger problem sets, one of the others may in fact be "best" for your specific use.

Upvotes: 3

rachitmanit
rachitmanit

Reputation: 334

Above reduced interpretations are as:

  1. O(log(m*n)) is equivalent to O(log m + log n)

  2. O(m+n) and O(log(m)*log(n)) are in reduced form itself

As logarithm of numbers are smaller than the number. Thus Order will be

O(log(m*n)) < O(log(m)*log(n)) < O(m+n)

That is log(m*n) is most efficient.

Remember it is a bigO. It would be better if you consider it for all possible output.

Upvotes: 6

Bathsheba
Bathsheba

Reputation: 234825

Write the first one as log m + log n. This is clearly better than m + n. It's also better than log(m) * log(n).

So the answer is log (m * n) is best.

Upvotes: 2

Grisha Weintraub
Grisha Weintraub

Reputation: 7986

The best is - log(m*n) (which is equivalent to log(m) + log(n))
Then - log(m)*log(n)
And then - m+n

Upvotes: 2

Related Questions