Why is the discrete logarithm problem assumed to be hard? This might be a quite stupid question: since a naive brute force algorithm to solve the discrete logarithm problem will only take O(n) time for a group G with order n, why is it assumed to be hard to solve? Doesn't hard mean no polynomial algorithm to solve in the context of cryptography?
While $O(n)$ is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in $O(n)$ but instead in $O(\log(n)) =  O(|n|)$ (e.g. expoentiation with square and multiply has $|n|$ multiplications and at most $|n|$ squaring operations).

Therefore, the basic consideration for $n$ should not be the number of group elements, but its logarithm (which is linear to the length of the numbers. In order to avoid the question: This is valid for any numeral system, regardless of its base). So if we have numbers of a group $\mathbb{G}$, we should set $n=\log_2|\mathbb{G}|$, and brute force algorithms require $O(2^n)$ operations.

Short version with less algebra:

Encrypting or signing something uses exponentiation as operation, and there are algorithms with complexity linear to the length of the numbers (in binary representation), and let's call the length $n$. If you want to test all possible values (aka brute force), there are $\approx2^n$ values to test, and this is exponential in the parameter $n$.