I have already posed the question on Math SE but I hope that people from QC community can help. I am starting studying QC, but first, I want to understand the classical view of algorithms. So in the following my question:
Here is the description of Deutsch-Jozsa problem: Let $f:\{0,1\}^n↦\{0,1\}$ be a function promised to be either constant or balanced ('balanced' means that f outputs as many $0$'s as $1$'s). Imagine that you try $k$ inputs (out of the $2^n$ available) and consistently find the same output. What is the probability that the function is actually constant? This link gives an answer as $1-1/2^{k-1}$. I am not able to reproduce this result and I have a prior question: how can the result not depend on $n$? Obtaining 5 equal results has a very different meaning if $n=10$ or $n=100$ isn't it?