3.1 Complexity growth and algorithmic cost

Why complexity comes before optimization

The lecture slides are right to begin with growth, not with micro-optimizations. When input size n becomes large, the way cost scales usually matters more than the exact machine that happens to run the code.

Big-O analysis is therefore a model of growth, not a stopwatch reading. Different machines will change constant factors, but they do not change whether the underlying pattern is linear, quadratic, or logarithmic.

That definition is a proof obligation. To use Big-O correctly, you need to show the bound with a valid threshold, not just say “it looks quadratic”.

The simplification rules are not shortcuts; they are the point

The tutorial slides repeatedly emphasize two rules:

• drop terms whose contribution becomes insignificant for large n,
• drop constant factors.

That is why expressions such as

0.1n^3 + 10000n^2 + n + 3

still simplify to $O(n^3)$. The cubic term eventually dominates everything else. Likewise,

(n^2 + n)/2

still has growth rate $O(n^2)$ because the 1/2 does not change the asymptotic shape.

Common growth classes in CSCI2520

The course slides and tutorials repeatedly use the same five classes.

• O(1): direct field access, known-pointer re-linking, simple arithmetic.
• O(log n): halving-style search, balanced-tree lookup, repeated division by 2.
• O(n): full scan over an array or linked list.
• O(n log n): divide-and-conquer with linear work per level.
• $O(n^2)$: nested scans, especially comparison-heavy double loops.

for (int width = 1; width < n; width *= 2) {
  for (int i = 0; i < n; i += 2 * width) {
    merge_block(i, width);
  }
}

The comparator widget is a visual aid, not a substitute for derivation. Use it to confirm intuition after you have already written down the growth model.

Reading complexity from code

The fastest way to analyze a function is usually to find the piece executed most often and count how many times that piece runs.

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

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

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

A concrete sorting example: selection sort

The tutorial deck uses selection sort to show where quadratic growth comes from. In pseudocode, the algorithm scans the remaining suffix to find the next minimum and then swaps it into place.

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 number of comparisons is roughly

(n-1) + (n-2) + ... + 1 = n(n-1)/2.

That sum is quadratic, so the algorithm is $O(n^2)$. The slide deck’s message is the same in words: doubling n makes the time roughly four times larger.

Comparison sorts versus non-comparison sorts

The sorting slides add an important refinement: merge sort, heapsort, and quicksort are all comparison sorts.

For comparison sorts, the worst-case number of comparisons has a lower bound of Ω(n log n). That means no comparison sort can beat that asymptotic barrier in the worst case.

If we want to sort faster than that lower bound, we have to avoid comparisons as the primary mechanism. That is exactly why counting sort and radix sort matter.

• Counting sort is linear time when the key range k is manageable.
• Radix sort repeatedly sorts by digit, typically using a stable subroutine.
• Counting sort is not an in-place comparison sort.

The practical lesson is not “every sort is the same”. The lesson is that the data domain and the operation model determine the correct complexity class.

Why lower terms and constants disappear

The tutorial’s simplification slides use expressions like

$N + 1 = O(N)$

and

$N^3 + 1000N^2 + N = O(N^3)$.

The reason is that the fastest-growing term controls the long-run growth. Lower-order terms still exist, but they stop mattering once n is large enough.

Best case, worst case, and average case

One complexity label is often not enough. The same algorithm may behave differently depending on the input arrangement.

• Best case describes the most favorable legal input.
• Worst case describes the most expensive legal input.
• Average case describes the expected cost under a probability model.

Binary search is a clean example.

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

When you read complexity claims in code, always ask which case is being quoted. A worst-case statement is the default unless the analysis explicitly says otherwise.

Divide-and-conquer and the n log n pattern

The slide deck mentions merge-sort-style behavior because it is the standard example of an n log n algorithm.

The usual reasoning has two layers:

• each round processes a linear amount of data,
• the number of rounds is about log n.

That is why the total becomes n log n.

A checklist for reading complexity from code

When you meet a new piece of code, the safest order is:

1. identify the operation that repeats most often;
2. count how many times the surrounding loop, recursion, or traversal executes;
3. separate constant work from size-dependent work;
4. simplify only after the counting step is explicit.

If you skip the counting step, you usually end up guessing. Good complexity work is slow reading first, short classification second.

When constants still matter

Asymptotic notation describes the long-run shape, but it does not say constants never matter. For small n, a simple $O(n^2)$ routine may still beat an O(n log n) routine with a very large hidden constant.

The disciplined conclusion is therefore two-part: first classify the growth correctly, then discuss whether the current input size is small enough that constant factors still influence the practical choice.

Cost of stack and queue operations

The previous section on ADTs gives useful concrete examples for this section. Once the representation is fixed, the same interface can have different costs.

• Array-based stack push / pop are typically constant time except when a resize happens.
• Linked-list queue enqueue / dequeue can be constant time when head and tail are maintained correctly.
• QueueLength() can be constant time if the length is stored, or linear time if it must scan the list.

That is why asymptotic analysis belongs next to implementation details, not apart from them.

Takeaway

Complexity analysis is a way to reason about scaling, not a way to guess which implementation “feels faster”. If you can identify the dominant repeated action, write the count, and simplify correctly, you can usually classify the algorithm without running it.