Suppose you are asked to compute the value of b^n for n, a large nonnegative integer. The simple solution is to compute the product b x b x ... x b involved n - 1 multiples. This takes time theta(n). Give a divide and conquer algorithm for the same problem that takes time theta(log(n)). you should state that the algorithm using pseudo-code. Follow this with a short analysis to show that you have achieved theta(log(n)) time.
Note: Your pseudo-code will be using "standard" multiples (i.e. you are not trying to make the simple multiply of two numbers any faster).© BrainMass Inc. brainmass.com March 21, 2019, 3:48 pm ad1c9bdddf
This solution provides a pseudocode for computing the value of b^n for n (a large nonnegative integer).