Big-oh complexity for logarithmic algorithms

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 开发者_Python百科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