Difficulty: Intermediate | Prerequisites: Basic algebra, familiarity with logarithms and exponents.
Matrices and Big O notation are two of the more applied topics on the CS 182 midterm. Matrix operations show up in linear algebra, graphics, and machine learning. Big O notation is the standard language for describing how algorithms scale, and it will follow you through every CS course from here on. Getting the order-of-growth hierarchy right is essential for comparing algorithms and answering "which is faster" questions on exams.
Matrix transposition swaps rows and columns, and matrix multiplication combines rows of the left matrix with columns of the right (dimensions must align). Big O notation classifies functions by their growth rate, giving you a ladder from O(1) up to O(n^n) that lets you compare algorithm efficiency at a glance.
Transpose (A^T)
The matrix obtained by flipping A over its diagonal: rows become columns and columns become rows. If A is m × n, then A^T is n × m.
Matrix Multiplication (AB)
The operation where each entry (i, j) of the product is the dot product of row i of the left matrix and column j of the right matrix. The number of columns in the left matrix must equal the number of rows in the right matrix. Think of it as "rows meet columns."
Big O Notation, O(f(n))
A classification that describes an upper bound on how a function grows as n increases. O(n²) means the function grows no faster than some constant times n² for large enough n. In simple terms, it tells you the worst-case scaling behaviour, ignoring constant factors.
Order of Growth
The ranking of complexity classes from slowest-growing (constant) to fastest-growing (n^n). Knowing this hierarchy lets you instantly compare two algorithms: O(n log n) beats O(n²) for large inputs, full stop.
Constant Time, O(1)
The running time does not depend on input size at all. A single array lookup is O(1).
Logarithmic Time, O(log n)
The running time grows proportionally to the logarithm of the input. Binary search is the classic example.
Linear Time, O(n)
The running time grows proportionally to the input size. Scanning every element of an array once is O(n).
Polynomial Time, O(n^c) for constant c
Running time grows as a power of n. O(n²) and O(n³) are the most common examples (nested loops).
Exponential Time, O(2^n)
Running time doubles with each additional input element. Brute-force solutions to NP problems often land here.
Factorial Time, O(n!)
Grows faster than exponential. Generating all permutations of n items is O(n!).
To transpose a matrix, swap its rows and columns. The element at position (i, j) moves to position (j, i).
Example:
A = [1 3 0 ; 3 4 −1] (2 × 3)
A^T = [1 3 ; 3 4 ; 0 −1] (3 × 2)
Row 1 of A becomes column 1 of A^T, and so on.
For AB to be defined, the number of columns in A must equal the number of rows in B. If A is m × n and B is n × p, the result is m × p.
Each entry (i, j) of the product is computed by taking the dot product of row i of the left matrix and column j of the right matrix: multiply corresponding entries and sum.
Worked example from the source:
A = [1 3 0 ; 3 4 −1] (2 × 3), B = [2 3 ; −2 5 ; −1 7] (3 × 2)
BA (3 × 2 times 2 × 3 = 3 × 3):
Entry (1,1): 2×1 + 3×3 = 11
Entry (1,2): 2×3 + 3×4 = 18
Entry (1,3): 2×0 + 3×(−1) = −3
Entry (2,1): −2×1 + 5×3 = 13
Entry (2,2): −2×3 + 5×4 = 14
Entry (2,3): −2×0 + 5×(−1) = −5
Entry (3,1): −1×1 + 7×3 = 20
Entry (3,2): −1×3 + 7×4 = 25
Entry (3,3): −1×0 + 7×(−1) = −7
Result: BA = [11 18 −3 ; 13 14 −5 ; 20 25 −7]
Note that matrix multiplication is not commutative: AB ≠ BA in general, and they may not even have the same dimensions.
This is the complete hierarchy from the source, ranked from slowest growth to fastest:
Rank | Name | Notation |
|---|---|---|
1 | Constant | O(1), O(30) |
2 | Double Logarithmic | O(log(log(n))) |
3 | Logarithmic | O(log(n)) |
4 | Polylogarithmic | O(log(n)²) |
5 | Fractional Power | O(n^(1/2)), where 0 < c < 1 |
6 | Linear | O(n), O(5n + 1) |
7 | Linearithmic | O(n log(n)) |
8 | Polynomial | O(n²), O(n^(3/2)) |
9 | Logarithmic-Polynomial | O(n² log(n)) |
10 | Exponential | O(2^n) |
11 | Logarithmic-Exponential | O(2^n log(n)) |
12 | Factorial | O(n!) |
13 | Super-exponential | O(n^n) |
The key insight: constant factors and lower-order terms do not matter for Big O. O(5n + 1) is the same class as O(n). What matters is the dominant term as n grows large.
Students assume matrix multiplication is commutative. It is not. AB and BA are generally different (and may not even be the same size). Always check dimensions before multiplying.
When multiplying matrices, students sometimes multiply element-by-element (Hadamard product) instead of using the dot-product-of-row-and-column rule. Element-wise multiplication is a different operation entirely.
Students often think O(2n) is exponential. It is not; O(2n) simplifies to O(n), which is linear. O(2^n) is exponential. The position of the n matters enormously.
Big O describes an upper bound, not an exact count. O(n²) does not mean the algorithm runs in exactly n² steps; it means the growth rate is at most proportional to n² for large n.
⚠️ The Big O order-of-growth hierarchy is a near-certain exam question. Memorise the ranking from O(1) through O(n^n), paying special attention to the middle tiers (polylogarithmic, fractional power, linearithmic) that students mix up.
⚠️ Matrix multiplication dimension checks are commonly tested: given A (m × n) and B (p × q), state whether AB is defined and give the resulting dimensions.
⚠️ Transposition is often a quick-marks question. Be able to write the transpose of a 2 × 3 or 3 × 3 matrix quickly and without errors.
⚠️ "Rank these functions by growth rate" is a classic exam problem. Practise ordering a mixed set of functions (n log n, 2^n, n², log n, n!, n^(1/2)) from slowest to fastest.
True or false: AB = BA for all matrices A and B. Answer: False. Matrix multiplication is not commutative.
If A is 3 × 2, what are the dimensions of A^T? Answer: 2 × 3.
Rank these from slowest to fastest growth: O(n²), O(log n), O(n log n), O(1), O(2^n). Answer: O(1) < O(log n) < O(n log n) < O(n²) < O(2^n).
True or false: O(100n) is the same growth class as O(n). Answer: True. Constant factors do not affect the Big O class.
Can you multiply a 2 × 3 matrix by a 2 × 3 matrix? Answer: No. The number of columns in the first (3) does not equal the number of rows in the second (2).
Q: Given A = [2 1 ; 0 3] and B = [1 4 ; 2 5], compute AB.
A: AB = [(2×1 + 1×2) (2×4 + 1×5) ; (0×1 + 3×2) (0×4 + 3×5)] = [4 13 ; 6 15].
Q: What is the transpose of B = [1 4 ; 2 5]?
A: B^T = [1 2 ; 4 5].
Q: Rank the following in order of growth: O(n^3), O(n log n), O(2^n), O(n^(1/2)), O(log(log(n))).
A: O(log(log(n))) < O(n^(1/2)) < O(n log n) < O(n^3) < O(2^n).
Q: An algorithm has a loop that runs n times, and inside it a nested loop that also runs n times. What is the Big O complexity?
A: O(n²). Each of the n outer iterations triggers n inner iterations, giving n × n = n² total.
Q: Is O(n² log n) faster or slower than O(n³) for large n?
A: Faster (slower growth). For large n, n² log n grows more slowly than n³ because log n grows more slowly than n.
Big O notation ties directly to the summation formulas from the Sets and Sums notes: when you evaluate a loop's total work as ∑(k=1 to n) k = n(n+1)/2, you are proving that the loop is O(n²). Geometric series give you the closed forms for divide-and-conquer recurrences. Matrix operations reappear in linear algebra courses and in algorithms that use matrix exponentiation (e.g. computing Fibonacci numbers in O(log n) time).
Matrix, transpose, transposition, matrix multiplication, dot product, row-column product, dimensions, Big O, Big-O, asymptotic notation, order of growth, time complexity, space complexity, constant time, logarithmic time, linear time, linearithmic, n log n, quadratic, polynomial, exponential, factorial, growth rate, algorithm analysis, complexity classes, upper bound, CS 182, Purdue, foundations of computer science