Why can't we always just pick the biggest term with big-O notation?

user_1578191 0
Viewed 219

I'm looking at Cracking the Coding Interview 6th edition page 49, example 8.

Suppose we have an algorithm that took in an array of strings, sorts each string, and then sort the full array. What would the runtime be?

If the length of the longest string is s and length of the array is a, the book says sorting each string would be:

O(a*s log s)

What I understand is the complexity depends on the upper bound in this case, so it should be:

O(s log s)

For example, if s is the length of longest string and s1, s2, s3 are lengths other strings, the complexity would be:

O(s log s + s1 log s1 + s2 log s2 + s3 log s3)

which is ultimately:

O(s log s)

because value of s is the highest. Why do we need to multiply if with a?

big-o time-complexity algorithm
2 Answers

You can only ignore the smaller terms if there's a constant amount of them.

The ability to ignore smaller terms actually follows from the fact that you can ignore constant factors, but this only works when you have a constant amount of smaller terms (otherwise the constant factor wouldn't be constant).

Intuitively:

What if you have 50000000000 strings of length 10? Some predefined factor of 10 log 10 doesn't sound right for the running time, you need that 50000000000 in there somewhere.

Mathematically:

Let's say you have f(n) + g(n), with g(n) being smaller than f(n) as n tends to infinity.

You can say that:

f(n) <= f(n) + g(n) <= f(n) + f(n) = 2.f(n)    (as n tends to infinity)

Now you've cancelled out g(n) and there's only a constant factor between 1 and 2 for f(n), which you can ignore with asymptotic notation, thus the complexity is simply O(f(n)).

If you have a variable number a of terms, you're going to have a.f(n) and you can't ignore that a.

The proof of a.f(n) = O(f(n)) (at least one way to prove it) involves picking a constant M such that |a.f(n)| <= M.f(n) from some value of n onward. No matter which value of M you pick, there can always exist a larger a (just M+1 would work), thus this proof fails.

user_17117960

As Dukeling points out, both a and s are parameters here.

So the runtime of your algorithm depends on both. Without more info about the relationship between the two, you can't simplify further. For instance, it doesn't sound like you're given a < s.

But say that you were given a < s. Then you could say that because your O(s log s) sorting operation needs to be performed a = O(s) times to sort all the strings in your array, the total is O(s^2 log s).

user_37571340
Related