My question stems from this: https://leetcode.com/problems/search-a-2d-matrix/
In math Log A + Log B = Log AB
Is this still valid for BigO notation?
Are two log searches Log A + Log B equal to one search of Log AB?
Big O - Is Log(A) + Log(B) == Log(AB) complexity?
Viewed 93
1 Answers
Yes, since you can manipulate the terms in Big-O notation in familiar algebraic ways, O(Log A + Log B) = O(Log AB).
When talking about two sequential searches, though, it might be more intuitive to leave it at O(Log A + Log B). You might want to simplify that to O(Log AB) if you're comparing to some other algorithm, or trying to find dominant terms.
Related