Hi again,
Few more problems I ran into calculating the Big-oh complexity. There are 2 problems which I cannot solve due to log base operations. Here are the two problems:
n = # of data items being manipulated
1) n^3 + n^2 log (base 2) n + n^3 log (base 2) n
2) 2n^3 + 1000n^2 + log (base 4) n + 300000n
I am confused when the logs have a base number. How do you go about calculating the complexity for these? Anyone care to explain how you get the complexity with a bit of detail if possible?
The base of the logarithm is irrelevant. You can just ignore it. Therefore:
1) It's O(n^3 log n) because that's the term that grows the fastest.
2) It's O(n^3) for the same reason.
The base is irrelevant because log base a (x) = log base b (x) / log base b (a), so any logarithm differs from another by a constant.
I suggest you read more about the properties of the logarithm here.
You don't need to "calculate complexity for a base number", you can just compare its growth rate to that of the other terms (see this graph of logarithm growth rates, to give you an idea )
Note that to solve these problems, you don't need to pay attention to the base of the logs.
O(x + y + z) === O(max(x,y,z))
So, decide which of the summed terms is largest and you can solve your problems.
In the calculation of asymptotic complexity, n is assumed to be very large and thus constants can be ignored. When you have a sum, only take into account the biggest term.
In your examples, this results in:
1) n^3 log(n)
2) n^3