Costs as functions of input size
Time complexity commonly counts elementary steps, while space complexity measures storage required by a computation. These are functions of input size rather than the seconds or memory reading from one execution. An algorithm's cost concerns a particular method; a problem's complexity concerns what resource bounds can be achieved across methods.
Size depends on encoding. The integer 1024 requires only eleven binary digits, whereas a loop repeated 1024 times performs far more than eleven iterations. Saying that work is linear in 'the number' is therefore ambiguous unless one distinguishes numerical value from representation length. The same distinction matters when comparing algorithms that process large integers.
Worst and average cases answer different questions
Worst-case analysis considers all inputs of a given size and establishes a maximum cost or an applicable upper bound. It does not say that every input incurs that cost. Average-case analysis instead takes an expectation over an input distribution. Its assumptions must be stated rather than hidden behind the word average.
For a sequential search of an unsorted list, a target at the first position requires one comparison; a target at the last requires n. If the target is guaranteed present and every position is equally likely, the expected count is (n+1)/2. If the target is usually absent, that average no longer describes the workload.
References: [2]
Growth rates and computational models
Asymptotic analysis compares growth as inputs become large. O(n²) is an upper-bound notation, not a claim that exactly n² steps occur, nor automatically the tightest possible bound. Constants and lower-order terms can dominate small inputs, so a better asymptotic order does not guarantee a faster measured run in every case.
Step counting also depends on the model. Single-tape and multiple-tape Turing machines agree on computability, yet may yield different time bounds for a task. One must say which operations are basic. Treating an arithmetic operation on an arbitrarily long integer as unit cost cannot be silently compared with a model charging for individual bit operations.
Termination is not practical feasibility
An exhaustive algorithm can always finish while requiring an unacceptable amount of time. Complexity classes refine the distinction: P contains decision problems solvable deterministically in polynomial time. This classification supports systematic comparison but is not an unconditional promise of practical speed.
NP problems admit polynomially bounded certificates that can be checked in polynomial time for yes instances; no certificate passes for a no instance. For SAT, a certificate is a satisfying truth assignment. SAT is NP-complete: every NP problem reduces to it in polynomial time, so SAT in P would imply P = NP. This remains open; NP-completeness does not establish an exponential lower bound or undecidability.
A very large exponent or constant can make a polynomial algorithm unusable. Conversely, restricted input families may be easy even when worst-case analysis is discouraging. Proving one algorithm slow does not prove that every algorithm for the problem must be slow. Practical assessment also considers input structure, size, accuracy requirements and measurements, while distinguishing established lower bounds from the upper bounds supplied by available algorithms.