Wednesday, September 19, 2012

Algorithm LAB_b) Write two recursive programs to compute Xn, where both X & n are integers, one computes it in O(n) time & the other in O(log n) time.

#include<stdio.h>
#include<stdlib.h>
long power(int, int);
int count;
int main()
{
    int x,y;
    long pow;
    printf("enter value of x\n");
    scanf("%d",&x);
    printf("enter power of x\n");
    scanf("%d",&y);
    count=0;
    pow=power(x,y);
    printf("the number of steps is %d\n",count);
    printf("the result is %ld\n",pow);
    return 0;
}
long power(int x, int y)
{
    count++;
    if(y==0)
        return 1;
    else if(y%2==0)
        return(power(x,y/2)*power(x,y/2));
    else
        return(x*power(x,y/2)*power(x,y/2));
}

No comments: