Best search algorithm to find condition within a range

[Ian Kelly]

On Wed, Apr 8, 2015 at 1:28 AM,  <jonas.thornvall at gmail.com> wrote:
> Den onsdag 8 april 2015 kl. 09:16:24 UTC+2 skrev Ian:
>> On Tue, Apr 7, 2015 at 4:35 PM,  <jonas.thornvall at gmail.com> wrote:
>> > I am not sure you guys realised, that althoug the size of the factors to muliply expands according to base^(exp+1) for each digitplace the number of comparissons needed to reach the digit place (multiple of base^exp+1) is constant with my approach/method.
>>
>> No it isn't. You do one comparison on every iteration of your while
>> loop, and you do one iteration for every digit. How is that constant?
>
> Ok the number of comparissons is linear for each digitplace not exponential.

In other words, the first part of your algorithm where you find the
largest digit place takes O(log n) operations. But the second part
where you do a search for each digit takes O(b * log n) operations, so
the overall number of operations is O(b * log n). If you replace the
linear search with a binary search, that's still O(log b * log n).

Meanwhile, the division method that I and others have repeatedly
suggested does only one comparison and one division per digit, which
is just O(log n).

Note that this analysis doesn't take into account the complexity of
the individual arithmetic operations, but that should affect either
algorithm equally.