If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?
It depends on the perspective from which one tackle the problem. Often, when dealing with numbers, people tend to give more importance to the number of bits. Why is that ? Simply because numbers problem comes from their size (number of digits or bits). Such algorithm for finding out whether a number N is prime or not
e. Itg.
- 0/1 knapsach problem: It runs in O(nW) time (see wikipedia). "n" being the number of items and "W" is the maximum weight. A large weight means a very large number, which is critical. A large number of items depends on the size of items, which reduces to W. The size of number grows exponentially when expressed in terms of bits (2x). For this reason people care more about size input data in terms of bits.
- is prime problem: An algorithm for finding out whether a number N is prime or not. It is quite easy to compute it for a 10 digit number, but harder as we go for large numbers. The number of bits here are important and grows exponentially.
- binary search: it runs in log2(n), but has a linear growth in terms of number of bits. It needs a really very big data set, which means a very big bit encoding so to make it impossible to run the algorithm in a reasonable amount of time.
In the first examples, there is quite easy to compute it for a 10significant difference between the real data size and data representation: We can easily give as input 300 digit number (relatively small), but harder as we go furtherit's encoding in binary code is TOO BIG, which influences the binary operations.
However in the case of "binary search", the different between data representation and real data size is constant.