SNOOTCHIEBOOCHEE
Oct5-08, 09:22 PM
1. The problem statement, all variables and given/known data
Show that for any fixed a and b, there is an algorithm to convert an n-digit number from
base a to base b with O(n^2) operations.
3. The attempt at a solution
Really i am completley lost here. Working backwards, i know to convert from base a to a base b you must use the division algorithm, which requires something on the order of (n^2) operations, but i really dont know how to show any of this.
Show that for any fixed a and b, there is an algorithm to convert an n-digit number from
base a to base b with O(n^2) operations.
3. The attempt at a solution
Really i am completley lost here. Working backwards, i know to convert from base a to a base b you must use the division algorithm, which requires something on the order of (n^2) operations, but i really dont know how to show any of this.