Growth rates and computational complexity

Four cards: four visits or sixteen?

Place four numbered cards on a table. A procedure that reads each card once makes four card visits. A different procedure considers every ordered pair of cards, including a card paired with itself. It makes sixteen pair visits: four choices for the first card and four for the second.

An algorithm is a specified procedure for turning permitted inputs into outputs. A problem states which outputs are correct; an algorithm gives one way to produce them. Before comparing procedures, ask whether they solve the same problem and count the same kind of work. Reading one card and testing a pair are different distinguished actions here.

The adjacent diagrams count those actions, not seconds. We omit setup, loop-condition tests and output costs from these first counts. Later we will say when such omitted work can be bounded and when a convenient count does not describe the full cost.

You can start with multiplication, powers and substituting values in formulas. Every required algorithm, logarithm and complexity-class idea is defined in this lesson. First follow the finite examples and the size parameter; return to the longer all-input arguments after you can explain what each table counts.

State the input size and the counted operation

Let n be a positive integer: n=1,2,3,… . In the card examples, n is the number of cards. A primitive operation is an action assigned a cost in the chosen model. Here one stated card or pair visit costs one unit. This does not assert that every real instruction, or every arithmetic calculation on arbitrary-size integers, has the same cost.

Let C(I) be the number of those units on a particular input I. If different inputs of the same size take different work, an exact formula must say which input it describes. When a size class has a largest cost, its worst-case cost T(n) is the maximum of C(I) over that class. For total encoded length over a fixed finite alphabet, every nonempty length class is finite; termination on each input then gives a finite maximum. A different size parameter, such as card count, may permit unbounded encodings, so existence of a worst-case maximum needs justification for its declared cost model.

For a list search that checks entries from left to right and stops at the first match, a first-position match costs one comparison. A missing match costs n comparisons. The worst case is n, while a particular successful search may cost less. An average-case claim needs a stated probability distribution; no such distribution is assumed here.

Operation counts and elapsed time answer related but different questions. Hardware, data access, implementation and representation affect seconds. If each counted action and the remaining work have suitable fixed-cost bounds, an operation-count argument can establish a running-time bound in that model. A measured chart by itself is not a proof for all larger inputs.

Count the allowed visits, not just the loops

One pass visiting each of n cards has count n. Visiting every ordered pair (i,j) with 1≤i,j≤n gives n rows of n visits, so the count is n². This includes (i,i) and both (i,j) and (j,i) when i≠j.

If only distinct unordered pairs are wanted, visit indices with i<j. The row counts are n−1,n−2,…,1,0. Each unordered pair has two distinct ordered versions, and there are n²−n ordered pairs with unequal indices. The count is therefore n(n−1)/2. For n=4 it is 6; for n=1 it is 0.

The number of written loops alone does not determine growth. Two nested loops can visit n² ordered pairs or n(n−1)/2 distinct pairs. If the inner loop always visits only three positions, the count is 3n instead. Read the bounds and the operation inside them.

For n binary choices, each choice has two possibilities, 0 or 1. Extending every partial string by both possibilities doubles the number of strings at each position. Starting with one empty string gives 2ⁿ complete strings. A procedure visiting each once has 2ⁿ candidate visits. Writing all n bits of each candidate would add a separate output cost of n·2ⁿ bit writes.

Repeated halving counts stages

Start with a positive integer k=n. While k≥1, visit k once and replace it by floor(k/2). The floor of a real number is its greatest integer not exceeding it. Thus 13 visits the values 13,6,3,1, then reaches 0 and stops. The count is 4, not 13 and not the number of written arrows including termination.

The base-two logarithm log₂n is the real exponent t for which 2ᵗ=n. For integer n≥1, let b be the unique positive integer with 2^(b−1)≤n<2ᵇ. Then b=floor(log₂n)+1. After j halvings the value is floor(n/2ʲ); it remains positive exactly for j=0,…,b−1. Therefore the loop makes b visits.

For n≥2, log₂n≤b≤log₂n+1≤2log₂n. These inequalities give a logarithmic upper and lower scale for this stage count. At n=1 the count is 1 although log₂1=0; an eventual bound may start at n=2. We will make that starting-threshold idea precise next.

This is a stage-count model. If each division handles a machine-sized integer at a bounded cost, the stages can model time. For arbitrary long binary integers, the cost of each division or read must be analysed too. A small number of stages does not eliminate the cost of obtaining or storing the input.

O, Ω and Θ describe eventual bounds

Let f(n) and g(n) be nonnegative real-valued functions on positive integer n, with g(n)>0 for all sufficiently large n. In a cost application f is the cost being bounded. The constants below must be fixed independently of n. A starting threshold n₀ is a positive integer.

We write f∈O(g), or conventionally f(n)=O(g(n)), when some constant c>0 and threshold n₀ satisfy f(n)≤c·g(n) for every integer n≥n₀. It is an eventual upper bound. The equality-style notation is shorthand for membership in a family of functions, not an exact equation f=cg.

We write f∈Ω(g) when some c>0 and n₀ satisfy c·g(n)≤f(n) for every n≥n₀. This is an eventual lower bound for that same chosen function f. Ω does not automatically mean a best-case analysis; O does not automatically mean a worst-case analysis. Specify f first.

We write f∈Θ(g) when both bounds hold: there are fixed a,b>0 and n₀ with a·g(n)≤f(n)≤b·g(n) for every n≥n₀. If the two original thresholds differ, use their maximum. Θ states a tight growth scale up to constant factors, not exact values or a limit ratio of one.

For f(n)=3n+2 and n≥1, 3n≤3n+2≤5n because 2≤2n. Thus a=3, b=5 and n₀=1 prove f∈Θ(n). For h(n)=n²+3n+2, the inequalities n²≤h(n)≤6n² hold for n≥1 since n≤n² and 1≤n². This proves h∈Θ(n²).

A bound can be true without being tight. The inequality n≤n² for n≥1 proves n∈O(n²). It does not prove n∈Θ(n²): a positive lower constant would require a·n²≤n, or a·n≤1, for every sufficiently large n. Given a>0, choosing an integer n>1/a defeats that inequality.

A fixed threshold permits early exceptions

Define f(n)=50+n for n<4, and f(n)=3n+2 for n≥4. The proposed upper envelope 5n fails at n=1,2,3. Nevertheless f(n)≤5n for every n≥4 by the earlier algebra. The witnesses c=5 and n₀=4 establish O(n). Early exceptions are permitted when the definition explicitly starts later.

You may not choose a new c for each n. Taking c=f(n)/g(n) at every point would make the upper comparison vacuous. One fixed pair c,n₀ must cover the entire infinite tail. Equally, checking twelve or a million inputs cannot alone establish a statement about every later integer.

A positive sum of polynomial terms can be bounded by its highest degree for n≥1. For example 2n³+7n+10 lies between 2n³ and 19n³, so it is Θ(n³). The coefficient 19 is a valid witness, even if a smaller one could also work. Eventual classification does not require the best constant.

For a fixed logarithm base q>1, log_q n=log₂n/log₂q. The denominator is a fixed positive constant, so changing that base leaves the Θ(log n) growth scale unchanged. Changing the exponent in 2ⁿ to 2^(2n) is different: their ratio is 2ⁿ, which is unbounded. Do not discard a factor inside an exponent as if it were outside.

Read both axes before comparing curves

The adjacent charts show exact values only at the integer inputs 1 through 12. The rows are the halving-stage count, n, n² and 2ⁿ. On the linear vertical scale the last exponential value is 4096, so the small counts sit close to the baseline. That compression is honest: all curves use one additive scale.

The second chart uses vertical coordinate log₂(value). Its baseline is value 1, not 0; equal vertical increments multiply the original value by a fixed factor. The 2ⁿ points lie on a straight line in these transformed coordinates because log₂(2ⁿ)=n. That shape does not make the original function linear.

The full table retains the original integer values and the scale labels state what distances mean. Guide segments between points do not define an algorithm on fractional card counts. A chart window can illustrate an inequality, but the algebra and quantified arguments prove its unlimited-domain conclusion.

At n=4, both n² and 2ⁿ equal 16. At n=8 their values are 64 and 256. A finite crossing does not settle which function grows faster eventually. Likewise a higher constant can make one linear-cost procedure slower on small inputs than a quadratic-cost one.

Why a fixed polynomial eventually loses to 2ⁿ

A polynomial-time upper bound has the form C·nᵏ for fixed C>0 and fixed nonnegative integer k, after a fixed threshold. For the simple comparisons here, constant, linear and quadratic are the cases k=0,1,2. An exponential like 2ⁿ eventually exceeds every such fixed polynomial. The finite charts are an illustration, not the proof.

Here is a counting proof of that last claim. Fix k≥0 and put r=k+1. Among all 2ⁿ binary strings of length n, count only those with exactly r ones. Choose their r positions: the number is n(n−1)…(n−r+1)/r!, where r!=1·2·…·r. Dividing by r! removes the different orders of choosing the same r positions.

When n≥2r, each of the r numerator factors is at least n/2. Hence 2ⁿ≥nʳ/(2ʳr!), so 2ⁿ/nᵏ≥n/(2ʳr!). The right side grows beyond every fixed C. Choose n larger than C·2ʳr!, as well as the stated thresholds. This proves that no fixed C can make 2ⁿ≤C·nᵏ hold on the entire tail.

This compares functions, not every possible algorithm for a problem. Seeing one exhaustive procedure visit 2ⁿ candidates does not prove that every correct procedure needs exponential time. A different method might avoid enumeration. Conversely being polynomial is a coarse theoretical criterion: n¹⁰⁰ or a huge constant can be impractical, and a small exponential instance can be manageable.

A number's value is not its input length

A positive integer M written in ordinary binary, without leading zeros, has b=floor(log₂M)+1 bits. Equivalently 2^(b−1)≤M≤2ᵇ−1. In unary it uses M repeated marks. Thus 31 is 11111₂, a five-bit numeral, or a row of thirty-one unary marks. The value is unchanged; the representation length is different.

A procedure that repeats exactly M times is linear in the numeric value M. Over b-bit positive inputs its worst value is 2ᵇ−1, so that repetition count is exponential in b. Calling it polynomial in the input length is valid for the unary representation's length M, but not for binary length b. Any conversion cost also belongs to a full algorithm analysis.

In a graph, n may instead mean the number of vertices. An n-by-n adjacency matrix has n² entries, while an adjacency-list representation records vertices and neighbour entries. For an undirected graph every listed edge appears at both endpoints. Counting visits in units of vertices and entries can be useful, but encoded labels and numbers consume bits too. State whether size means vertices, stored words or total bits.

For complexity classes we use the total length N of a finite binary input and a fixed bit-operation model, equivalently a standard deterministic machine model up to polynomial simulation. We do not assign unit cost to multiplying integers of unlimited length. A high-level step count needs an implementation-cost argument before it becomes a bit-time theorem.

Checking a candidate differs from finding one

A decision problem asks a yes-or-no question on each encoded input. For example, given a Boolean formula, is there an assignment making it true? A Boolean variable has value false or true, encoded here by 0 or 1. The symbol ¬ means not, ∨ means or, and ∧ means and.

Consider (x₁∨¬x₂)∧(x₂∨x₃)∧(¬x₁∨¬x₃). Each parenthesised clause requires at least one true literal, and all three clauses must hold. A literal is a variable or its negation. The assignment 001 makes the clauses true,true,true, whereas 000 fails the middle clause. These results are checked by the complete table beside this explanation.

A certificate is a finite proposed witness for a yes answer. Here it is the assignment's three bits. Our full verifier checks all six literal occurrences, without early stopping, and then combines the clause results. Testing all eight possible assignments to find one is a different procedure. A rejected certificate does not establish that no accepted certificate exists.

For arbitrary formulas of this form, choose an input encoding with an explicit inventory recording every declared variable, together with the clauses and their variable references. The verifier visits the encoded literals and checks those references. An assignment has one bit per inventory entry, so its length is at most a fixed multiple of the total input length. A binary header declaring the variable count alone would not establish that bound. Even straightforward bit-level lookup and evaluation take polynomial time in this explicit encoding length; this finite six-check illustration is not itself a proof of a universal unit-cost implementation.

Read P and NP as whole problem classes

P is the class of decision problems for which some deterministic algorithm gives the correct yes or no answer on every input and has a polynomial worst-case time bound in total bit length N. Deterministic means the specified next action is fixed by its current state and input. The algorithm and polynomial bound are fixed for the whole problem, not chosen anew for each input.

NP is the class of decision problems with a deterministic polynomial-time verifier and polynomial-length certificates for yes instances. More precisely, there is a fixed polynomial bound p such that an input I is a yes instance exactly when some certificate c of length at most p(|I|) makes the verifier accept. The verifier runs within a polynomial bound in |I| on these bounded certificates; longer certificates can be rejected at the length check.

Both directions matter. Every yes instance must have at least one accepted certificate. Every no instance must have no accepted certificate. Verifying a random candidate quickly is not enough if it can falsely certify a no instance, or if some yes instances require certificates exceeding the polynomial bound. NP abbreviates nondeterministic polynomial time, not non-polynomial time.

P⊆NP: a polynomial solver can be used as a verifier that ignores an empty certificate and simply runs the solver. Thus NP includes problems already known to have polynomial algorithms. The question whether P=NP remains open. A fast verifier is not a proof that finding a certificate requires exponential time, nor is it a proof that a polynomial solver exists.

For context, a polynomial reduction from decision problem A to B is a polynomial-time transformation mapping each input to an input of B with the same yes/no answer. B is NP-hard when every problem in NP reduces to it; it is NP-complete when it is also in NP. A polynomial solver for an NP-complete problem would therefore put all of NP in P. This lesson defines that implication, but does not claim a completeness proof for its small example.

Tractable often informally means admitting a polynomial-time algorithm. It does not promise fast execution for every realistic input or machine. Complexity theory classifies unlimited families of encoded instances under explicit models; practical performance also needs constants, memory, input structure and measurement. Return to the exact counting rule whenever a broad label hides what was actually counted.

Worked examples

Try it yourself

1. A procedure visits each of eight cards once. What does the distinguished-action model count?

   Show the answer and reasoning

   Eight card visits.

   It counts the stated visits, not seconds or omitted setup and loop-condition tests.

2. For each of n items, an inner loop makes exactly three visits. Is its count n²?

   Show the answer and reasoning

   No. Its count is 3n.

   The inner bound is fixed at three. Two written loops do not by themselves force a quadratic count.

3. How many pairs i<j can be visited among five cards?

   Show the answer and reasoning

   10.

   There are 5·4=20 unequal ordered pairs. Each unordered pair occurs in two orders, so 20/2=10.

4. For n=1, compare the ordered-pair and distinct-unordered-pair counts.

   Show the answer and reasoning

   They are 1 and 0.

   The only ordered pair is (1,1); no pair can satisfy 1≤i<j≤1.

5. List the positive loop-entry values for floor-halving from 8 and give the visit count.

   Show the answer and reasoning

   8,4,2,1; four visits.

   The next value 0 ends the loop. At the exact power 8=2³, the count is 3+1.

6. Is n∈O(n²)? Does that imply n∈Θ(n²)?

   Show the answer and reasoning

   Yes to the upper bound, no to the tight bound.

   n≤n² for n≥1. Any fixed positive lower witness a would require a·n≤1 for arbitrarily large n, which fails.

7. Give witnesses proving n²+2n+1∈Θ(n²).

   Show the answer and reasoning

   Use lower constant 1, upper constant 4 and n₀=1.

   For n≥1, n²≤n²+2n+1≤n²+2n²+n²=4n².

8. Our piecewise count exceeds 5n at n=1,2,3. Does that disprove its O(n) witness starting at n₀=4?

   Show the answer and reasoning

   No.

   The witness only asserts f(n)≤5n for every n≥4. Its first three exceptions lie outside that quantified range.

9. Why is choosing c=f(n)/g(n) separately for each n not an O proof?

   Show the answer and reasoning

   The definition requires one fixed positive c and one threshold covering every later n.

   An input-dependent constant supplies a different statement at every point and can hide unbounded ratios.

10. On the base-two logarithmic vertical chart, what does the baseline represent, and why can 2ⁿ look straight?

    Show the answer and reasoning

    The baseline represents value 1. Its plotted height is log₂(2ⁿ)=n.

    Equal vertical increments multiply original values. Straightness after this transformation does not imply linear growth of the original function.

11. How many bits write the positive integer 8 without leading zeros? How many unary marks write it?

    Show the answer and reasoning

    Four bits, 1000₂, and eight unary marks.

    2³≤8<2⁴, so b=4. Encoding length is not the same as value.

12. Does a proved O(N¹⁰⁰) bit-time algorithm automatically run quickly on practical inputs?

    Show the answer and reasoning

    No.

    The bound is polynomial, but its large exponent and hidden constant can still make execution impractical.

13. A left-to-right search stops at the first match in n entries. Compare a first-position match and a missing match.

    Show the answer and reasoning

    The counts are 1 and n comparisons, and the worst case is n.

    Worst case quantifies over all permitted inputs of that size. One favourable input does not establish a one-comparison worst case.

14. Does NP mean that every problem in it lacks a polynomial solver?

    Show the answer and reasoning

    No. NP means nondeterministic polynomial time, and P⊆NP.

    A polynomial solver itself supplies a verifier that ignores an empty certificate. Whether all NP problems have polynomial solvers remains open.

15. What must an NP verifier do on a no instance for every certificate within its length bound?

    Show the answer and reasoning

    Reject every such certificate.

    Acceptance of any certificate would falsely certify a yes answer. A yes instance instead needs at least one accepted bounded certificate.

16. An exhaustive algorithm tries all 2ⁿ binary assignments. Does that prove its problem has no polynomial algorithm?

    Show the answer and reasoning

    No.

    It describes one procedure. A lower bound ruling out every polynomial procedure would need a separate argument.

What to carry forward

• State the input domain, size parameter and charged operation before giving a count.
• Exact work on one input, worst-case work over a size class and measured seconds are different quantities.
• O is an eventual upper bound, Ω a lower bound and Θ a two-sided bound for the specified function, with fixed constants and thresholds.
• Read the vertical scale: logarithmic plotting changes geometric appearance, not the original values or their growth class.
• An exponential exceeds every fixed polynomial eventually, but one exhaustive algorithm does not prove a problem-wide lower bound.
• Numeric value, stored items and total encoded bits can give different cost scales. Unlimited-size arithmetic requires its own cost analysis.
• P and NP classify whole decision problems. NP requires short certificates and reliable polynomial verification; P⊆NP and P versus NP remains open.