x raise to n in log2n time
I wrote a program for this and then compared the algo with the O(n) algo. when i am trying to print the time taken , o(log2n) is more than o(n). can anyone explain why?
o/p : 2 ^ 20 = 1048576
time taken : 709727
----------------
2 ^ 20 = 1048576
time taken : 123759
below is the code :
import java.util.HashMap;
public class SquareExmp {
public static void main(String[] args) {
int x = 2, n = 20;
long t1=System.nanoTime();
System.out.println(x+" ^ "+n+" = "+getSquareLog2n(x, n));
long t2= System.nanoTime();
t2=t2-t1;
System.out.println("time taken : "+(t2));
System.out.println("----------------");
long t3=System.nanoTime();
System.out.println(x+" ^ "+n+" = "+getSquareLinear(x, n));
long t4= System.nanoTime();
System.out.println("time taken : "+(t4-t3));
}
static long getSquareLog2n(long x, long n) {
if(n==0)
return 1;
else if (n==1)
return x;
else{
long a= getSquareLog2n(x, n/2);
long b = a*a;
if(n%2==0)
return b;
else
return b*x;
}
}
static long getSquareLinear(long x,long n){
if(n==0)
return 1;
else if (n==1)
return x;
else
return x*getSquareLinear(x, n-1);
}
}
context switching
- Naveen August 15, 2012