Question

Calculate the Big-O time complexity. Show work

1. n^2 + 3n + 2

2. (n^2 + n)(n ^2 + π/2 )

3. 1 + 2 + 3 + · · · + n − 1 + n

Answer 1

Calculate the Big-O time complexity of the following:

• The upper bound notation for the function F(n) is provided by the Big-OH (O) notation. For the all suitable large value of n, the function F(n) = O(g(n)) if we can prove following statement.

• O(g) is the set of function from non-negative integers to positive real numbers such that for some real constant C >0 and some non-integer constant number n₀:

F(n) ≤ C * g(n) + n₀ for all n ≥ n₀

(1) n² + 3n + 2

Time complexity: O(n²)

Description:

F(n) ≤ C * g(n) + n₀ for all n ≥ n₀

⇒ n² + 3n + 2 ≤ n² + 3n + n ;n ≥ 2

⇒ n² + 3n + 2 ≤ n² + 3n + n ;n ≥ 2

⇒ n² + 3n + 2 ≤ n² + 4n ;n ≥ 2

⇒ n² + 3n + 2 ≤ n² + n² ;n² ≥ 4n

⇒ n² + 3n + 2 ≤ 2n²       ;n² ≥ 4n

So, g(n) = n² and C = 2

F(n) = O(g(n))

F(n) = O(n²)

(2) (n² + n)(n² + π/2)

Time complexity: O(n⁴)

Description:

(n² + n)(n² + π/2) = n⁴ + n³ + (π/2)n² + (π/2)n

F(n) ≤ C * g(n) + n₀ for all n ≥ n₀

⇒ n⁴ + n³ + (π/2)n² + (π/2)n  ≤  n⁴ + n³ + (π/2)n² + n² ; n² ≥ (π/2)n

⇒ n⁴ + n³ + (π/2)n² + (π/2)n  ≤  n⁴ + n³ + (π)n²   ; n² ≥ (π/2)n

⇒ n⁴ + n³ + (π/2)n² + (π/2)n  ≤  n⁴ + n³ + n³ ; n³ ≥ (π)n²

⇒ n⁴ + n³ + (π/2)n² + (π/2)n  ≤  n⁴ + 2n³    ; n³ ≥ (π)n²

⇒ n⁴ + n³ + (π/2)n² + (π/2)n  ≤  n⁴ + n⁴    ; n⁴ ≥ 2n³

⇒ n⁴ + n³ + (π/2)n² + (π/2)n  ≤ 2n⁴    ; n⁴ ≥ 2n³

So, g(n) = n⁴ and C = 2

F(n) = O(g(n))

F(n) = O(n⁴)

(3) 1 + 2 + 3 + · · · + n − 1 + n

Time complexity: O(n²)

Description:

1 + 2 + 3 + · · · + n − 1 + n = n(n + 1)/2 = n²/2 + n/2

F(n) ≤ C * g(n) + n₀ for all n ≥ n₀

⇒ n²/2 + n/2 ≤ n²/2 + n²   ; n² ≥ n/2

⇒ n²/2 + n/2 ≤ (3/2)n² ; n² ≥ n/2

So, g(n) = n² and C = 3/2

F(n) = O(g(n))

F(n) = O(n²)