Let $A$ be a known $m \times n$ matrix, $x$ an unknown $1 \times n$ column vector, and $b$ a known $1 \times n$ column vector. For the following cases, what is the time complexity to solve the system of linear equations $Ax = b$? What algorithm achieves that time complexity? Assume that at least one solution exists.
Case 1: m < n.
Case 2: m = n.
Case 3: m > n.
Either Gaussian elimination with partial pivoting or (householder) QR followed by backward/forward substitution run in $O(mn \min(m,n))$ arithmetic operations and produce a solution to a consistent system of linear equations. When properly implemented on computers using floating point arithmetic, these algorithms almost always produce answers about as accurate as you could expect them to.
If you’re a theoretical computer scientist, you may care not just about the number of arithmetic operations but the complexity of performing these arithmetic operations on the possibly increasingly complicated-to-describe rational numbers produced in Gaussian elimination. I’m not aware of the best exact complexity in general, but it is known that linear systems are solved in polynomial time in the bit complexity required describe the input matrix and right-hand side (in any of the “natural” encodings) by using Gaussian elimination. (This question might have some insights you find interesting.)