# What are min and max numbers of inputs needed to know whether the 4-bit classical Deutsch-Jozsa algorithm is balanced?

What are the minimum and maximum number of inputs you would need to check to know whether this 4-bit classical Deutsch-Jozsa oracle is balanced or constant?

Now, let us look at the worst case. Instead of taking 4, let's say we have an n-bit oracle. For this oracle you have $$2^n$$ different inputs. Imagine that you have made $$2^{n-1}$$ queries with distinct bit strings and got the same result i.e. either all 0s or 1s. At this point, you still can not comment on the nature of the function whether it is balanced or constant as it may be so that it has value 1 or value 0 for all the bit strings you input.
This implies that you must need atleast 1 more query to test whether it is balanced or constant. Thus, in this worst case scenario, you would need at max $$2^{n-1} + 1$$ number of queries.