Decision boundary: where the classifier flips its prediction. Linear models always produce a hyperplane. k-NN follows local majority — produces complex, non-linear boundaries.
Trade-off: linear models are simple/regularized/fast; k-NN/trees/NNs adapt to non-linear patterns at the cost of more data and risk of overfit.