Answer to Question #327860 in Algorithms for Nath

Question

Determine the complexity of the expression

(I) 5n² + 3nlogn + 2n + 5 that log n <= n for n >= 1

(II) 5n⁴ + 3n³ + 2n² + 4n + 1

Answer 1

(I) As log n <= n, for n>=1, therefor nlog n <= n², as far as n <= n² and 1 <= n² for n>=1.

So 5n² + 3nlogn + 2n + 5 <= 5n² + 3n² + 2n² + 5n² = 15n² for n>=1.

Finally: complexity is O(n²)

(II) 1 <= n <= n² <= n³ <= n⁴ for n >= 1. So 5n⁴ + 3n³ + 2n² + 4n + 1 <= 5n⁴ + 3n⁴ + 2n⁴ + 4n⁴ + n⁴ = 15n⁴ for n >= 1

Finally: complexity is O(n⁴)