Question

Give a pseudo-code description of the O(n)-time algorithm for computing the power function p(x,n).Also draw the trace of computing p(3,3)using this algorithm?

Answer 1

p(x,n)

1. if(n==0) [if power is 0]

2. then result =1.

3.else

4. { result=1.

5. for i=1 to n.

6. { result = result * x. } [each time we multiply x once]

7. return result.

8. }

Let's count p(3,3)

3
`\\eq`0, so come to else part.

i=1: result = result *3 = 3

i=2: result = result *3 = 9

i=2: result = result *3 = 27

Step-by-step explanation:

here the for loop at step 4 takes O(n) time and other steps take constant time. So overall time complexity = O(n)