Big O proof with sqrt and log

I am having trouble figuring out how to prove that

t(n) = sqrt(31n + 12n log n + 57)

is

O(sqrt(n) log n)

I haven't had to deal with square root's in big O notation yet so I am having lots of trouble with this! Any help is g开发者_JS百科reatly appreciated :)

---

Big O notation is about how algorithm characteristics (clock time taken, memory use, processing time) grow with the size of the problem.

Constant factors get discarded because they don't affect how the value scales.

Minor terms also get discarded because they end up having next to no effect.

So your original equation

sqrt(31n + 12nlogn + 57)

immediately simplifies to

sqrt(n log n)

Square roots distribute, like other kinds of multiplication and division, so this can be straightforwardedly converted to:

sqrt(n) sqrt(log n)

Since logs convert multiplication into addition (this is why slide rules work), this becomes:

sqrt(n) log (n/2)

Again, we discard constants, because we're interested in the class of behaviour

sqrt(n) log n

And, we have the answer.

Update

As has been correctly pointed out,

sqrt(n) sqrt(log n)

does not become

sqrt(n) log (n/2)

So the end of my derivation is wrong.

---

Start by finding the largest-degree factor inside of the sqrt(), which would be 12nlogn. The largest-degree factor makes all the other factors irrelevant in big O terms, so it becomes O(sqrt(12nlogn)). A constant factor is also irrelevant, so it becomes O(sqrt(nlogn)). Then I suppose you can make the argument this is equal to O(sqrt(n) * sqrt(logn)), or O(sqrt(n) * log(n)^(1/2)), and eliminate the power on logn to get O(sqrt(n)logn). But I don't know what the technical justification would be for that last step, because if you can turn sqrt(logn) into logn, why can't you turn sqrt(n) into n?

---

Hint: Consider the leading terms of the expansion of sqrt(1 + x) for |x| < 1.