Complexity analysis - take consideration of non lo

问题:

Just a quick preparation for my exam, for example I have:

f(x) = 5x<sup>2</sup> + 4x * log(x) + 2

Would the big O be O(x<sup>2</sup> + x * log(x)) or should I take consideration of non-logarithmic coefficients such as 5 or 4?

Likewise, consider this code

for (int i = 0; i < block.length; i++)
    for (int j = 0; j < block.length;  j++)
        for (int k = 0; k < 5; k++)
             g(); //assume worst case time performance of g() is O(1)

So would the big O be O(5n²) or O(n²)?

回答1:

Complexity for f(x) = 5x^2 + 4xlogx + 2 is O(x^2) because

O(g(x) + k(x)) = max(O(g(x), k(x))
// and O(X^2) > O(xlogx)

//additionally coeffs are disregarded
O(c*g(x)) = O(g(x))

So if you have a sum you just select the largest complexity as at the end of the day, when n goes to infinity the largest component will give the most computational load. It also doesn't matter if you have any coeffs because you try to roughly estimate what's going to happen.

---

For your other sample see reasoning below

for (int i = 0; i < block.length; i++)
    for (int j = 0; j < block.length;  j++)
        for (int k = 0; k < 5; k++)
             g(); //assume worst case time performance of g() is O(1)

First convert loops into sums and work out the sums from right to left

Sum (i=0,n)
    Sum(j=0, n)
        Sum(k=0, k=5)
            1

Counter of O(1) from 1 to 5 is still O(1), remember you disregard coeffs

Sum(k=0, k=5) 1 = O(5k) = O(1)

So you end up with the middle sum, which counts a function of O(1) n times, this gives the complexity of O(n)

Sum(j=0, n) 1 = O(n)

Finally you get to the leftmost sum and notice that you count n n-times, i.e. n+n+n..., which is equal to n*n or n^2

Sum (i=0,n) n = O(n^2)

So the final answer is O(n^2).

回答2:

O(x**2) because:

lim n^2 if (x->8) = 8

lim 5n^2 if (x->8) = 8

8 is infinity

but if you have the sum of few expressions you need to understood the fastest growing function. it will be an answer on you question.

any other constant before expression will give you the same answer. In that case you should use asymptotic analysis I may give you an advice. If you faced the sum of few function you need:

• decompose your expression on the components
• imagine the plots of each element
• understood the fastest growing element which not exceeded the infinite

this element will give you answer