Alder Alder for n 1-bit numbers
suppose adding two numbers with a
and bits b
can be done in O (max {a, b}). we want to add numbers n
(n 1-bit numbers ie add n 0 or 1). the cost of this altogon varies from permutation of the input to another permutation. What is the best and worst case scenario for this algorithm?
I came across this issue as an old poll on a computer course.
We have two solutions:
1- Best case and worst case can be in O (n)
2- Best in O (n) and Wost case in O (n lg n)
Can anyone describe any pesudocode or algorithm for more than two orders of magnitude?
Answer 1 - best and worst case - O (n). Best case when all bits are 0, order n - 1 is required, or just put O (n). In the worst case, when all the bits are 1, the actual order is the sum of n * (lg n - lg i) / 2 ^ (lg n - lg i) i from n to 0. When i approaches 0, the resulting expression will be small and therefore can be ignored. Thus, the expression has the form n / 2 + n / 4 * 2 + .... Again, linear growth with n.
Adding more details:
Best case, when all bits are 0, adding them will never result in more than 1 digit missing. (i.e. always gives 0). so the order is O (n)
In the worst case, when all the bits are 1, adding the first 2 bits would take O (1). The result would be 10. Now adding it with another bit would take O (2), and thus the order might increase in the worst case. Suppose we split the input set into 2 pairs of numbers and add them, in the first iteration all pairs will require O (1) and lead to 10. There are n / 2 pairs, so this is O (n / 2). In the second iteration, we will split the first set of iteration results into 2 pairs of numbers and add them. (Note that now all nos are 10). So the order would be n / 4 * O (2). that is O (n / 2). Thus, this should continue until the result set is exhausted. But when the value of n is very large, the contribution from 3 iterations forward can be ignored. So it's just O (n / 2) + O (n / 2) i.e. O (n)
source to share