Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of the $n!=6$ orderings of the 3 numbers. I.e., there is one solution for the case $A>B>C$, another solution for $A>C>B$, etc. (the case $A>C=B$ can be solved by any one of these two solutions).
Thinking of the case $n=4$, it seems that the only way is, again, to consider all $n!=24$ different orderings and develop a different solution for each case. While the solution in each particular case is fast, the program itself would be very large. So the runtime complexity of the problem is small, but the "development time" complexity or the "program size" complexity is very large.
This prompted me to try and prove that my problem cannot be solved by a short program. So I looked for references for similar proofs.
The first concept that I found is Kolmogorov complexity; however, the information I found about this topic is very general and includes mostly existence results.
Can you describe a specific, real-life problem $P$, such that any program solving $P$ on an input array of size $n$ must have a size of at least $\Omega(f(n))$, where $f(n)$ is some increasing function of $n$?
Since the answer obviously depends on the selection of programming language, assume that we program in Java, or in a Turing machine - whichever is more comfortable for you.
Every undecidable problem trivially satisfies this requirement because it has no solution at all. So I am looking for a decidable language.