[Introduction to Algorithms, CLRS] Exercises 2.2-1

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.2-1

Express the function n3 / 1000 - 100n2  - 100n + 3 in terms of Θ notation. 

Answer:

The answer’s going to be Θ(n^3). (n to the 3)

Writing e for the original expression, 

Θ(e) = Θ(max(n^3/1000, −100n^2, −100n, 3)).

 This will equal to Θ(max(n^3 , n^2 , n, 1)).

As Θ(1) < Θ(n) < Θ(n^2 ) < Θ(n^3 ), Θ(max(n^3 , n^2 , n, 1)) = Θ(n^3 ).

Source: https://web.cs.wpi.edu/~guttman/cs2223/hw1_clrs.pdf