Algorithm growth and asymptotic bounds

Ask what is being counted

Two programs can return the same answer while doing different amounts of work. Algorithm analysis describes how resource use changes with input size. It does not predict a stopwatch reading from a loop count alone. You will choose a cost model, count a few bounded loops, distinguish O, Ω and Θ, and keep input cases separate from growth bounds.

Prerequisites: C variables, initialized arrays, valid indices, loops, functions and the earlier distinction between total recursive calls and simultaneously active frames. We use n for the number of selected input elements, not their sum or maximum value. An array capacity is allocated storage; a logical length n says how many elements this call uses. Later search and sorting lessons use this vocabulary. This is an introduction, not a full course in complexity, recurrence solving or lower-bound proofs for all algorithms.

A cost model states what counts as work. Examples include key comparisons, array-element visits or executions of a specified loop body. Count the same operation consistently. One “loop iteration” is not automatically one machine instruction. For ordinary fixed-size C integers, we treat each simple comparison, assignment and arithmetic operation as constant-cost. Arbitrarily large integers, disk access and network requests would need other models.

A time-cost function f(n) must identify both the algorithm and the input-case rule. A maximum over all admitted inputs of size n is worst-case cost; a minimum is best-case cost. Average-case cost requires a specified probability distribution; it is not generally the arithmetic mean of best and worst costs.

A teaching bound versus an asymptotic family

The runnable examples below deliberately accept only 0 <= n <= 8 so that every index and arithmetic result is safe. A fixed finite domain alone cannot distinguish asymptotic classes in a meaningful growth analysis. When we discuss growth as n becomes large, we mean the same loop pattern in a family of implementations with adequate capacity and representable counters. The literal CAP=8 program is not run beyond its contract.

The math and the safe program serve different purposes: exact small traces establish what a loop counts; a symbolic formula describes the scalable pattern. Do not remove the input guards merely to imitate an “infinite n” argument. C integer overflow and resource limits do not disappear when notation is used.

Upper, lower and tight bounds

Let f(n) be a nonnegative cost and g(n) a comparison function that is positive for sufficiently large integer n. Constants below are positive and independent of n. Threshold n0 is fixed too.

• f is O(g): upper bound. There exist C and n0 such that 0 <= f(n) <= C*g(n) for every n >= n0.
• f is Ω(g): lower bound. There exist c and n0 such that 0 <= c*g(n) <= f(n) for every n >= n0.
• f is Θ(g): tight two-sided bound. There exist c, C and n0 such that 0 <= cg(n) <= f(n) <= Cg(n) for every n >= n0.

Equivalently, Θ(g) means both O(g) and Ω(g). It does not mean f(n) is exactly g(n), that all inputs take identical time, or that constants vanish from actual runtimes. The threshold allows finitely many small sizes to behave differently.

O gives an upper bound, which need not be tight. A linear function can also be O(n squared); that statement is true but less informative than Θ(n). Ω is a lower bound on the chosen cost function, not a synonym for best case. O is not a synonym for worst case. First choose best, worst, a specific input pattern or a stated average; then bound that function.

Worked trace 1: prove a bound rather than guess one

Suppose a precise cost model gives f(n) = 3n + 2 for integer n >= 0. For n >= 1:

3n <= 3n + 2 <= 5n.

Choose c = 3, C = 5 and n0 = 1. These constants prove f is Θ(n). The upper inequality alone proves O(n); the lower one proves Ω(n). Since n <= n squared for n >= 1, the same f is also O(n squared). That does not make its tight growth quadratic.

Why is it not Θ(n squared)? The ratio f(n)/(n squared) = 3/n + 2/(n squared) becomes arbitrarily small as n grows. No fixed positive c can keep c*n squared below f(n) for all sufficiently large n. In particular, being O(n squared) does not supply the missing quadratic lower bound. These statements concern this f, not an empirical timing sample.

Three complete bounded C11 probes

The first function sums the first n elements and counts element visits. The second counts pairs of indices i < j, not key comparisons. The third counts repeated integer-halving iterations. Their counters measure selected events, not every CPU instruction. All three ignore data values when deciding how many loop iterations to perform.

#include <stdio.h>

enum { CAP = 8 };

typedef struct {
    int ok;
    int sum;
    int visits;
} SumResult;

int valid_length(int n) {
    return n >= 0 && n <= CAP;
}

/* Caller supplies CAP initialized int slots, each from -9 through 9. */
SumResult prefix_sum(const int a[], int n) {
    SumResult result = {0, 0, 0};
    if (!valid_length(n)) {
        return result;
    }
    result.ok = 1;
    for (int i = 0; i < n; i = i + 1) {
        result.sum = result.sum + a[i];
        result.visits = result.visits + 1;
    }
    return result;
}

int pair_steps(int n) {
    if (!valid_length(n)) {
        return -1;
    }
    int steps = 0;
    for (int i = 0; i < n; i = i + 1) {
        for (int j = i + 1; j < n; j = j + 1) {
            steps = steps + 1;
        }
    }
    return steps;
}

int halving_steps(int n) {
    if (!valid_length(n)) {
        return -1;
    }
    int remaining = n;
    int steps = 0;
    while (remaining > 0) {
        remaining = remaining / 2;
        steps = steps + 1;
    }
    return steps;
}

int main(void) {
    const int values[CAP] = {4, -1, 7, 0, 3, -2, 1, 5};
    int n = 4;
    SumResult result = prefix_sum(values, n);
    if (!result.ok) {
        return 1;
    }
    printf("sum: %d visits: %d\n", result.sum, result.visits);
    printf("pairs: %d halves: %d\n", pair_steps(n), halving_steps(n));
    return 0;
}

Exact output:

sum: 10 visits: 4
pairs: 6 halves: 3

Contracts and the small amount of record syntax

The prefix_sum caller supplies a live array of exactly CAP initialized int elements, each between -9 and 9. It remains unchanged during the call. const int a[] refers to that original storage through C's array-parameter convention; it does not copy the array or discover its capacity. NULL, dangling storage and out-of-range element values are outside this storage/value contract. The function separately checks n at runtime before reading any element. The empty prefix n=0 needs no element read, but the same existing storage is still supplied.

typedef struct defines a record with ok, sum and visits fields. SumResult result = {0,0,0} initializes them in declaration order. A function returns that record by value; the caller uses dots such as result.visits to select fields. ok=1 indicates success; ok=0 indicates rejected length, so the other initialized fields must not be treated as an answer. pair_steps and halving_steps return -1 on invalid n; all valid event counts are nonnegative, so no valid count conflicts with that status.

enum { CAP = 8 }; defines an integer constant. && means logical AND; ! tests for zero. A for loop initializes a variable, tests its condition, runs the body if true, then performs the update. Both i and j are local loop variables. / 2 on a nonnegative integer discards the fractional part. printf's %d prints an int and \n starts a line. The two counter helpers only read their copied n, so their calls in one printf do not modify shared state.

For valid n, prefix reads only indices 0 through n-1; its sum lies from -72 to 72. pairs counts at most 28 events. Halving takes at most four iterations and reaches zero. Index updates such as i+1 are at most 8. These fit even C's minimum required int range. Invalid lengths -1 or 9 return failure without starting a loop. Do not extrapolate the small-int arithmetic proof to unbounded input sizes.

Worked trace 2: exact counts from the loops

For n=4, prefix_sum reads values 4,-1,7,0: running sums 4,3,10,10 and visits 1,2,3,4. It examines exactly n elements even if an early element or running sum is zero.

pair_steps(4) executes its body for pairs (0,1), (0,2), (0,3), (1,2), (1,3), (2,3): six pairs. The outer index contributes 3,2,1,0 inner iterations. In general the count is (n-1)+(n-2)+...+1+0 = n(n-1)/2. The product is a mathematical formula; the C implementation increments a bounded counter instead of computing an unbounded product.

halving_steps(4) changes remaining from 4 to 2 to 1 to 0, hence three iterations. For n=5 it goes 5,2,1,0, also three: integer division does not preserve the discarded fraction. For positive n, the exact count is floor(log2 n)+1. log2 n is the exponent x for which 2 to the power x equals n; floor means rounding downward to an integer. The empty n=0 case gives zero iterations and is handled separately, without taking log2 0.

For the scalable patterns, prefix visits are Θ(n). Pair executions are Θ(n squared): for n>=2, n squared/4 <= n(n-1)/2 <= n squared/2. Halving iterations are Θ(log n) as n grows (take a threshold n>=2). Changing the fixed logarithm base only changes a constant factor. These are tight bounds on the counted events.

The complete loops also perform tests and index updates. Those add constant work per relevant iteration; they do not change these large-n time classes under the stated cost model. Zero pair-body executions at n=1 does NOT mean the function uses zero total time: it still validates, initializes and checks loops. Return values are not automatically full runtime counts.

Worked trace 3: choose the case before using a bound

Consider ordinary linear search that checks equality at indices 0,1,... and stops at its first match. Count key-equality comparisons, for n>=1. On an input whose first element matches, the count is 1. On an input where the only match is last, or no element matches, the count is n. For n=4 those examples give 1 versus 4 comparisons.

Both functions have upper and lower bounds. The best-case function is O(1), Ω(1), and also the loose O(n). The worst-case function is O(n), Ω(n), and Θ(n). Saying “linear search is Ω(n)” without naming the case can therefore be misleading: its best-case function is not Ω(n), while its worst-case function is. A worst-case lower bound says the maximum cost is large enough; it does not say every input has that cost.

Average comparisons require assumptions about absent targets, matching positions and their probabilities. For example, under a model where a target is always present once and each of the n positions is equally likely, this comparison count averages (n+1)/2. This is a sufficient model for that mean, not the only possible distribution with the same mean. Do not assume that distribution silently. Search implementations and duplicate rules are taught in the next lesson.

Auxiliary space is not total allocated storage

State what is excluded. Here auxiliary space means working storage beyond the already supplied input and the returned output; the runtime call stack counts as working storage. A constant number of scalar variables and a constant-size local record take Θ(1) auxiliary space in these iterative helpers. n visits do not imply n simultaneously stored work items.

The main demonstration already reserves eight input elements, regardless of n. In a scalable version, an input array of n elements occupies Θ(n) input storage even when the helper's auxiliary space is Θ(1). A separate array that copies all n input elements would require Θ(n) additional storage; declaring it “temporary” would not make it constant space. The driver and the algorithm need not have the same space bound.

For a simple recursive chain with one waiting call per decreasing length, up to n+1 source-level invocations may be active. In the conventional unoptimized call-stack model with constant storage per frame, this is Θ(n) auxiliary stack space, even if each individual call declares only a few scalars. This is not a statement of exact physical bytes in an optimizing compiler. Balanced recursion, total call count and maximum active depth require separate analysis; use the earlier frame-count lesson rather than counting all calls as simultaneous memory.

A precise analogy

Imagine counting the number of doors an inspection procedure checks. Looking at every one of n doors gives a linear count; checking every unordered pair of doors gives a quadratic count; repeatedly discarding about half a remaining candidate group gives a logarithmic number of rounds. How long an individual check takes is a separate assumption. The notebook's simultaneous working pages describe auxiliary space, not the total number of doors checked. This analogy concerns counted operations and stored work, not actual processor timing or an automatic guarantee about every program.

Key box

• Specify input size, the counted operation, the case rule and the scalable family.
• O is an eventual upper bound; Ω is an eventual lower bound; Θ supplies both.
• Bounds need not be exact formulas. An O bound may be loose.
• Best/worst/average describe inputs; they are not aliases for Ω/O/Θ.
• Average-case claims need a probability model.
• Nested loops need actual bounds; repeated halving differs from decrementing by one.
• Auxiliary space counts simultaneous extra storage, including active call frames under the stated model.
• Safe finite C examples do not authorize unbounded indices, overflow or stack depth.

Try it first, then check

1. Prove a tight bound for f(n)=7n+4. Answer: for n>=1, 7n <= 7n+4 <= 11n, so c=7, C=11, n0=1 prove Θ(n). O(n squared) is also true but loose.
2. Trace pair_steps(3) and halving_steps(3). Answer: pairs (0,1),(0,2),(1,2) give 3; remaining 3,1,0 gives 2 halving iterations. The functions measure different events and their returned integers do not report CPU time.

Six original practice questions

Choose exactly one option. These are original introductory exercises, not previous-year questions or a full syllabus assessment.

1

For f(n)=3n+2 as integer n grows, which statement is correct?

A. It is Θ(n squared) because it is O(n squared). B. It is Θ(n), and O(n squared) is also a true but loose upper bound. C. It is not O(n) because of the extra +2. D. It is Θ(1) because 3 and 2 are constants.

2

Which interpretation of Ω(g(n)) is correct for a specified nonnegative cost function f(n)?

A. It always describes the algorithm’s best-case inputs. B. It says every input has exactly g(n) cost. C. It is an upper bound that applies only to worst case. D. It gives an eventual lower bound by a positive constant multiple of g(n), regardless of which input-case function was selected.

3

Linear search stops at its first match. Count key-equality comparisons over all admitted arrays/targets of size n>=1, including absent targets. What are the best- and worst-case tight bounds?

A. Θ(1) and Θ(n) B. Ω(n) and O(1), because Ω means best and O means worst C. Θ(n) and Θ(n), because the array has n elements D. Θ(1) and Θ(log n), because every search halves its input

4

For the exact safe probes, what do pair_steps(5) and halving_steps(5) return?

A. 25 and 5 B. 15 and 2 C. 10 and 3 D. 10 and 5

5

An iterative helper reads n elements from an already supplied input array, returns one scalar and uses only a fixed number of scalar working variables. Under the lesson’s convention, what is its auxiliary-space growth?

A. Θ(n), because reading n elements stores n new copies B. Θ(1), while the supplied input storage may separately be Θ(n) C. Θ(n squared), because both input and loop index exist D. It must be Θ(log n) because loops reuse variables

6

Which assumption justifies (n+1)/2 average key comparisons for ordinary first-match linear search on n>=1 elements?

A. Only knowing best cost 1 and worst cost n, with no input distribution B. Every query is absent C. Every query matches the first position D. The target is present exactly once, and each of the n positions is equally likely

Worked answers

1: B

A is incorrect: a quadratic upper bound does not prove a quadratic lower bound; f(n)/n² tends to zero.

B is correct: for n>=1, 3n<=f(n)<=5n, and 5n<=5n².

C is incorrect: for n>=1 the +2 fits within the constant-factor upper bound 5n.

D is incorrect: the term 3n increases without bound as n increases.

2: D

A is incorrect: best case is a choice of cost function; its lower bound is a separate question.

B is incorrect: a bound is an inequality, not an exact formula or an all-input equality.

C is incorrect: Ω is lower, while O is upper; either can bound a specified best- or worst-case function.

D is correct: some fixed c>0 and n0 make c*g(n)<=f(n) for every n>=n0.

3: A

A is correct: first-position equality needs one comparison; an absent target or last-only match needs n.

B is incorrect: it confuses bound direction with input-case selection and reverses the actual growth.

C is incorrect: stopping at the first matching element avoids examining the remaining n-1 elements.

D is incorrect: ordinary linear search advances by one element and does not discard half the candidates.

4: C

A is incorrect: pairs require i<j, not all 5×5 ordered positions; halving is not decrement-by-one.

B is incorrect: adding self-pairs gives 15, but i<j excludes them; the halving sequence has three iterations.

C is correct: pair counts are 4+3+2+1+0=10; remaining follows 5→2→1→0, three steps.

D is incorrect: the pair count is right, but division by two reaches zero in three iterations, not five.

5: B

A is incorrect: reading sequentially does not allocate a separate copy for every element.

B is correct: simultaneous working storage is constant; the convention excludes the supplied input and returned output.

C is incorrect: coexistence of two kinds of storage does not multiply their sizes.

D is incorrect: no logarithmically growing stack or buffer is described; the working variables are fixed in number.

6: D

A is incorrect: best and worst endpoints alone do not determine the probabilities or average.

B is incorrect: an absent target takes n comparisons every time.

C is incorrect: every query then takes one comparison, not generally (n+1)/2.

D is correct: costs 1 through n have equal probability, giving (1+2+...+n)/n=(n+1)/2.

Next step and scope

Apply this vocabulary next to linear/binary search and insertion/selection sort. This original foundation does not cover all Algorithms or change an existing course examination year. Hindi explanations support learning.