3.1 Complexity growth and algorithmic cost

Compare the lower-order term with the proposed dominant term:

Equivalently, $n^2/n=n$ grows without bound. The conclusion is not that the linear term vanishes from an exact formula. It is that the linear term becomes negligible relative to $n^2$, which supports a tight $\Theta(n^2)$ statement when the leading coefficient is positive.

int x = a + b;
int y = x * 2;
return y;

Under the stated fixed-width RAM model, each statement executes once and costs constant time. Their sequential costs add to another constant, so the fragment is $\Theta(1)$. This conclusion would need revision if, for example, a and b represented unbounded integers whose arithmetic cost grows with their bit length.

int sum(const int a[], int n) {
   int total = 0;
   for (int i = 0; i < n; i++) {
      total += a[i];
   }
   return total;
}

The body runs exactly $n$ times and has constant cost, so the total is $an+b=\Theta(n)$ for fixed constants $a>0$ and $b$. The lecture deck's Average function has the same structure: one full pass plus a final division. Calling such a helper is therefore a $\Theta(n)$ operation, not an automatically constant-cost source line.

int countPairs(int n) {
   int c = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         c++;
      }
   }
   return c;
}

For this particular program, the inner statement runs exactly $n\cdot n$ times, so the cost is $\Theta(n^2)$. The conclusion follows from the bounds, not merely from seeing two loop keywords.

Function calls can create the same product invisibly. In the source deck's naive variance routine, an $n$-iteration loop calls Average(array,n) on every iteration. A $\Theta(n)$ helper repeated $n$ times gives $\Theta(n^2)$ work; the final average adds only $\Theta(n)$. Computing the mean once before the loop changes the composition to several consecutive linear passes, whose costs add to $\Theta(n)$. If temporary storage is used, its auxiliary-space cost must be reported separately.

The same counting method handles loops that are not rectangular. If the inner loop runs from i + 1 to n - 1, its execution count is $\sum_{i=0}^{n-2}(n-i-1)$, a triangular sum. If an index doubles on every iteration, the condition $2^k<n$ gives $k=\Theta(\log n)$ executions. If the inner bound is i, the count is $\sum_i i$ rather than $n$ times a fixed quantity. Thus the relevant object is the iteration space described by the bounds, not the number of syntactic loop headers.

void selectionSort(int a[], int n) {
   for (int i = 0; i < n - 1; i++) {
      int min = i;
      for (int j = i + 1; j < n; j++) {
         if (a[j] < a[min]) min = j;
      }
      if (min != i) {
         int tmp = a[i];
         a[i] = a[min];
         a[min] = tmp;
      }
   }
}

The exact comparison count is $n(n-1)/2$, not an approximation. Replacing $n$ by $2n$ changes the leading quadratic expression by a factor approaching four; replacing it by $10n$ gives a factor approaching one hundred. Those ratios explain the lecture timing pattern, while the theorem—not the timing table—proves the asymptotic class.

To prove $(n^2+n)/2=O(n^2)$, choose $C=1$ and $n_0=1$. For every $n\ge1$,

For a tight result, also note $(n^2+n)/2\ge n^2/2$. Thus the expression is $\Theta(n^2)$. Giving both inequalities makes clear why $O(n^3)$ would be true but uninformative.

int binarySearch(const int a[], int n, int target) {
   int left = 0, right = n - 1;
   while (left <= right) {
      int mid = left + (right - left) / 2;
      if (a[mid] == target) return mid;
      if (a[mid] < target) left = mid + 1;
      else right = mid - 1;
   }
   return -1;
}

The precondition is a sorted random-access array with constant-time key comparisons. A first-probe match gives best-case $\Theta(1)$. In the worst case, each iteration leaves at most half the candidates, so after $k$ iterations at most $n/2^k$ remain. Reaching one candidate requires $k=\Theta(\log n)$. The midpoint formula avoids overflowing left + right.

An unsuccessful search has the same logarithmic worst-case bound: the candidate interval keeps shrinking until it becomes empty. If duplicate keys are allowed, this version may return any matching position; finding the first or last match requires a modified invariant. Binary search also does not make an unsorted search logarithmic for free. Sorting the data first costs additional work, so that preprocessing is justified only when its cost can be shared across enough later queries. On a linked list, locating the midpoint is not constant time, so the random-access assumption is part of the complexity claim rather than an implementation detail.

Suppose an algorithm splits a problem in half until subproblems have size one, and every recursion level performs $\Theta(n)$ total combination work. There are $\Theta(\log n)$ levels, so the level costs add to $\Theta(n\log n)$. Equivalently, the recurrence $T(n)=2T(n/2)+\Theta(n)$ has that solution for powers of two, with ceilings and floors changing only constants for general $n$.

The premise “linear work per level” must be proved. Divide-and-conquer alone does not guarantee an $n\log n$ bound.

This level argument counts time, not automatically space. If the two recursive calls are completed one after the other, the active recursion depth is $\Theta(\log n)$, while temporary merge storage may still require $\Theta(n)$ auxiliary space. A different implementation or parallel execution can change the space profile without changing the recurrence used for total work, so the resource being bounded must remain explicit.