Time Complexity

If an algorithm has a time complexity of O(n²), can we also say it is O(n³)?

Yes, if an algorithm has a time complexity of O(n²), we can also say it is O(n³).

Big-O notation (O) defines an asymptotic upper bound. It tells us that an algorithm's runtime grows no faster than a certain rate as the input size (n) grows.

The O-notation (big O) defines an upper bound on the growth rate of a function. Informally, O(g(n)) represents the set of all functions that have a lower or the same order of growth as g(n), within a constant multiple, as n approaches infinity.

If an algorithm's time complexity is O(n²), it means its running time, let's call it t(n), is bounded above by some constant multiple of n² for all sufficiently large n. Formally, there exist positive constants c and n₀ such that t(n) ≤ c * n² for all n ≥ n₀.

Since n² grows slower than n³ (i.e., n² is of a lower order of growth than n³), any function t(n) that is bounded above by n² will also be bounded above by n³.

For instance, if an algorithm takes 5n² + 10n operations, it is O(n²). Since 5n² + 10n is also less than, say, 1 * n³ for large n, it is also O(n³). The O-notation provides an upper bound, and a looser upper bound (like n³) is still a valid upper bound even if a tighter one (like n²) exists.

If an algorithm has a time complexity of Θ(n), can we also say it is O(n²)?

Yes, if an algorithm has a time complexity of Θ(n), we can also say it is O(n²).

Big-Theta notation (Θ) defines a tight bound. This means the algorithm's runtime grows at the same rate as the specified function. It's both an upper and a lower bound.

The Θ-notation (big theta) defines a tight bound on the growth rate of a function. Informally, Θ(g(n)) represents the set of all functions that have the same order of growth as g(n), within a constant multiple, as n approaches infinity.

If an algorithm's time complexity is Θ(n), it means its running time t(n) is bounded both below and above by constant multiples of n for all sufficiently large n. Formally, there exist positive constants c₁, c₂, and n₀ such that c₂ * n ≤ t(n) ≤ c₁ * n for all n ≥ n₀.

Since O(n²) implies that t(n) is bounded above by a constant multiple of n², and we know from the Θ(n) definition that t(n) ≤ c₁ * n, we can easily establish the O(n²) relationship.

For n ≥ 1, we know that n ≤ n². Therefore, if t(n) ≤ c₁ * n, then t(n) ≤ c₁ * n² for n ≥ max(1, n₀). This directly satisfies the definition of O(n²).

Any function in a lower efficiency class (like Θ(n)) will also be in an upper efficiency class (like O(n²)).

For each of the following functions, indicate how its value changes if its input n is increased eightfold:

This question relates to how functions scale with input size.

• a) log₂n: If n is increased eightfold to 8n, the new value is log₂(8n). Using logarithm properties, log₂(8n) = log₂8 + log₂n = 3 + log₂n. So, the value increases by 3. log₂ n increases by just 1 with a twofold increase in n.

• b) n: If n is increased eightfold to 8n, the new value is 8n. The value increases eightfold.

• c) n²: If n is increased eightfold to 8n, the new value is (8n)² = 64n². The value increases 64-fold. Quadratic function n² increases fourfold with a twofold increase in n.

• d) n³: If n is increased eightfold to 8n, the new value is (8n)³ = 512n³. The value increases 512-fold. Cubic function n³ increases eightfold with a twofold increase in n.

• e) 2ⁿ: If n is increased eightfold to 8n, the new value is 2⁸ⁿ = (2ⁿ)⁸. The value is raised to the power of 8. Value of 2ⁿ gets squared ((2ⁿ)²) with a twofold increase in n.

Compare the order of growth for the following pairs of functions. State whether the first function has a smaller, larger, or the same order of growth as the second:

The order of growth refers to how the function scales as the input size n goes to infinity, ignoring constant multiples and lower-order terms.

We can use informal comparison or limits.

a) n(n+1) and 200n⁴ :

• n(n+1) = n² + n. As n approaches infinity, the dominant term is n². This function is in Θ(n²).
• 200n⁴. As n approaches infinity, the dominant term is 200n⁴. This function is in Θ(n⁴).
• Comparing n² and n⁴, the function n⁴ grows faster than n².
• Therefore, the first function n(n+1) has a smaller order of growth than the second function 200n⁴.

b) 2ⁿ⁻¹ and 2ⁿ:

• 2ⁿ⁻¹ = 2ⁿ * 2⁻¹ = ½ * 2ⁿ.
• The two functions differ only by a constant multiplicative factor (½).
• Therefore, the first function 2ⁿ⁻¹ has the same order of growth as the second function 2ⁿ.

For the following functions, express their complexity using Big O, Big Omega, and Big Theta notation:

For a function t(n), O(g(n)) provides an upper bound, Ω(g(n)) provides a lower bound, and Θ(g(n)) provides a tight bound (same order of growth),. For polynomials with a positive leading coefficient, the order of growth is determined by the highest degree term. The simplest function g(n) is typically used in these notations.

a) f(n) = 10n³ + 8 :

• This is a polynomial of degree 3. The highest degree term is 10n³.
• The function's order of growth is the same as n³.
• Using Big Theta: f(n) ∈ Θ(n³) . This means it's bounded above and below by constant multiples of n³ for large n.
• Using Big O: Since f(n) is in Θ(n³), it is also in O(n³). It is bounded above by a constant multiple of n³ for large n.
• Using Big Omega: Since f(n) is in Θ(n³), it is also in Ω(n³). It is bounded below by a positive constant multiple of n³ for large n.

b) g(n) = 100n + 5:

• This is a polynomial of degree 1. The highest degree term is 100n.
• The function's order of growth is the same as n.
• Using Big Theta: g(n) ∈ Θ(n). It's bounded above and below by constant multiples of n for large n.
• Using Big O: Since g(n) is in Θ(n), it is also in O(n). It is bounded above by a constant multiple of n for large n.
• Using Big Omega: Since g(n) is in Θ(n), it is also in Ω(n). It is bounded below by a positive constant multiple of n for large n.

Arrange the following functions in ascending order of their growth rates:

(n-2)!, 5lg(n+100)¹⁰, 2²ⁿ, 0.001n⁴+3n³+1, ln²n, ³√n, 3ⁿ.

We need to determine the dominant term or recognized growth class for each function and then order them.

• 5lg(n+100)¹⁰ = 50 lg(n+100): This is logarithmic. Logarithms with different bases belong to the same efficiency class (Θ(log n)) .

• ln²n = (ln n)²: This is a squared logarithmic function. Θ(log² n). As n grows, log²n grows faster than log n .

• ³√n = n^(1/3): This is a polynomial with a fractional exponent. Θ(n^(1/3)). Polynomials grow faster than logarithms .

• 0.001n⁴+3n³+1: This is a polynomial of degree 4. The highest degree term dominates for large n. Θ(n⁴) . Polynomials grow faster than n^(1/3).

• 3ⁿ: This is an exponential function with base 3. Θ(3ⁿ). Exponential functions grow faster than any polynomial.

• 2²ⁿ = (2²)ⁿ = 4ⁿ: This is an exponential function with base 4. Θ(4ⁿ). Comparing exponential functions aⁿ and bⁿ where a < b, bⁿ grows faster than aⁿ. So 4ⁿ grows faster than 3ⁿ.

• (n-2)!: This is a factorial function. Θ((n-2)!). Factorial functions grow much faster than exponential functions,,.

Arranging them in ascending order of growth rates:

1. 5lg(n+100)¹⁰ (Θ(log n))
2. ln²n (Θ(log² n))
3. ³√n (Θ(n^(1/3)))
4. 0.001n⁴+3n³+1 (Θ(n⁴))
5. 3ⁿ (Θ(3ⁿ))
6. 2²ⁿ (Θ(4ⁿ))
7. (n-2)! (Θ((n-2)!))

This matches the ordering given in the source.

Using the definitions of O, Θ, and Ω, determine whether the following assertions are true or false. Justify your answers.

a) n(n+1)/2 ∈ O(n³) b) n(n+1)/2 ∈ Θ(n³) c) n(n+1)/2 ∈ Ω(n)

Recall the formal definitions:

• t(n) ∈ O(g(n)) if t(n) ≤ c * g(n) for n ≥ n₀ for some positive constant c and non-negative n₀
• t(n) ∈ Ω(g(n)) if t(n) ≥ c * g(n) for n ≥ n₀ for some positive constant c and non-negative n₀
• t(n) ∈ Θ(g(n)) if c₂ * g(n) ≤ t(n) ≤ c₁ * g(n) for n ≥ n₀ for some positive constants c₁, c₂ and non-negative n₀

The function in question is t(n) = n(n+1)/2 = ½n² + ½n. This function has an order of growth of n². Thus, t(n) ∈ Θ(n²).

a) n(n+1)/2 ∈ O(n³) :

• True. O(n³) is an upper bound. Since ½n² + ½n grows slower than n³, it is bounded above by a constant multiple of n³ for large n.

• Justification using definition: We need to find c > 0 and n₀ ≥ 0 such that ½n² + ½n ≤ c * n³ for all n ≥ n₀. For n ≥ 1, ½n² + ½n ≤ ½n³ + ½n³ = n³. We can choose c=1 and n₀=1.

b) n(n+1)/2 ∈ Θ(n³) :

• False. Θ(n³) implies the same order of growth as n³. ½n² + ½n has a lower order of growth than n³.

• Justification using definition: We need to show that there do not exist positive constants c₁, c₂ and nonnegative n₀ such that c₂ * n³ ≤ ½n² + ½n ≤ c₁ * n³ for all n ≥ n₀. Specifically, the lower bound c₂ * n³ ≤ ½n² + ½n cannot hold for any positive c₂ for sufficiently large n, because n³ grows faster than n².

c) n(n+1)/2 ∈ Ω(n) :

• True. Ω(n) is a lower bound. Since ½n² + ½n grows faster than n (for large n), it is bounded below by a positive constant multiple of n for large n.

• Justification using definition: We need to find c > 0 and n₀ ≥ 0 such that ½n² + ½n ≥ c * n for all n ≥ n₀. For n ≥ 0, ½n² + ½n ≥ ½n. We can choose c=½ and n₀=0.