Give a big-O estimate for each of these functions.?

Question

For the function g in your estimate f(x) is O(g), ues a simple function g of smallest order.

a. (n^3 + (n^2)log n)((log n) + 1) + ((17 log n) + 19)(n^3 + 2)

b. (n^n + n(2^n) + 5^n)(n! + 5^n)

Any help you can give is greatly appreciated, and I'll vote best answer.

Answer 1

The big O estimate is the behaviour of the function when n tends to infinity. This means that you only retain the largest terms.
Note that n! goes as n^n.

a. (n^3 + (n^2)log n)((log n) + 1) + ((17 log n) + 19)(n^3 + 2)
=> (n^3) (log n) + (17 log n) (n^3)
=> O (n^3 log n)

b. (n^n + n(2^n) + 5^n)(n! + 5^n)
=> (n^n) (n!) => O (n^2n)

Answer 2

The approach in these problems is to pick out the most rapidly growing term in each sum
and discard the rest (including the multiplicative constants).

(a) (n^3 + n^2 log n)(log n + 1) = n^3 log n + n^3 + (n·log n)^2 + n^2 log n
(17 log n + 19)(n3 + 2) = 17 n^3 log n + 19 n^3 + 34 log n + 38.

The dominant terms in the two factors are O(n3 · log n + 17 n^3 log n), which is the
same as O(n3 · log n).

(b) The dominant terms in the two factors are nn and n!, respectively. Therefore this is
O(n^n·n!).