1.Show that X^62 can be computed with only 8 multiplications.
2.Programs A and B are analyzed and found to have worst-case running times no greater than 150NlgN and N^2, respectively. Answer the following questions, if possible:
1. Which program has the better guarantee on the running time, for large values of N (N > 10,000)?
2. Which program has the better guarantee on the running time, for small values of N (N < 100)?
3. Which program will run faster on average for N = 1000?
4. Is it possible that program B will run faster than program A on all possible inputs?
Well we would not start to teach you mathematics here, finally this is a programming forum, you may ask these questions in some mathematics or physics forum. But in short, there are other ways to calculate x^y than to multiply x y times, which is even not possible when y is not an integer. For practical programming, it's also sometimes useful to use function tables, may make things very fast.
