This (https://en.m.wikipedia.org/wiki/Discrete_logarithm) Wikipedia article confuses me. If you have the equation a = g^n (mod P), and g, P and a are all known, then how does a brute force solving for n algorithm run in exponential time, as this article states. Shouldn't it be linear, or am I reading this article wrong?
In computational complexity, the computational complexity is typically expressed as a function of the size $n$ (in bits) of the input, and the complexity is expressed as a function of $n$.
You may be right to consider since sorting algorithms are using the number of elements however the context is important; the number of bits is more natural in cryptography since we measure the security in bits.
Therefore it is exponential in the input size where the input is measured in bits.
Saying it is linear while considering the number of possible values is misleading in cryptography since you will end up a difficulty in agreement with the cryptographers. Therefore use number of bits.