如何证明10n = O(n²)？Big O复杂度证明方法问询

Hey there! Let's walk through how to prove that the function 10n belongs to the time complexity class O(n²) using the formal definition of Big O notation, and we'll evaluate the candidate parameters you provided to find the valid pair.

First, Recap the Formal Big O Definition #

A function f(n) is in O(g(n)) if there exist positive constants c and n₀ such that for every integer n ≥ n₀, the inequality:
f(n) ≤ c * g(n)
holds true.

For our case, f(n) = 10n and g(n) = n². We need to find which of your candidate (c, n₀) pairs satisfy this rule.

Evaluate Each Candidate Pair #

Let's go through each option one by one:

• c = 0, n0 = 1: Invalid. The definition requires c to be a positive constant—0 doesn't meet this requirement, so we can immediately rule this out.
• c = 1, n0 = 1: Invalid. For n=1, 101 = 10, while 1(1²) = 1. 10 > 1, which violates the inequality. Even for larger n like n=5, 50 > 25, so this pair doesn't work.
• c = 2, n0 = 5: Valid! Let's prove it:
  For all n ≥ 5, divide both sides of the inequality 10n ≤ 2n² by n (since n is positive, the inequality direction stays the same):
  10 ≤ 2n
  Simplify to 5 ≤ n—which is exactly our n₀ condition (n ≥5). For every n ≥5, this holds:
  • n=5: 105 = 50, 2(5²)=50 → 50 ≤50 ✔️
  • n=6: 106=60, 2(6²)=72 →60 ≤72 ✔️
  • Any n>5: 2n² grows much faster than 10n, so the inequality will always hold.
• c =1, n0=9: Invalid. For n=9, 109=90, while 1(9²)=81. 90>81, which breaks the inequality. We'd need n₀=10 for c=1 to work, but that's not what's listed here.

Final Takeaway #

The valid parameter pair is c=2, n0=5, and using it we've formally proven that 10n is indeed O(n²).

内容的提问来源于stack exchange，提问作者Faizan Saeed