deepa02.ag
BAN USER- 2 Answers 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?
- deepa02.ag August 05, 2012
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);
}
}| Flag | PURGE - 3 Answers regarding google recruitment
hi. i want to gather info regarding how can i get into google ? rght now its very early for me as i have just 2.5 yrs of experience with infosys. but i want to gear up from now. basically i am looking for info like wat kind of profile one need to have to fetch a call from google. I have been working on java platform and i m from non CS background.is it like only CS people get there. kindly put some light .thanks.
- deepa02.ag August 02, 2010| Flag | PURGE
@abhaya-hey thanks for ur response. now i can at least start off.
can anyone plz suggest some good basic books on algos.
ya i got ur point.but y binary search.is it because we hav a sorted array ? i guess linear search is easier to implement.please correct if i am wrong. Thanks
- deepa02.ag July 30, 2010
hey.. thanks for the post. i am actually very willing to get into the top notch companies ,esp. Google. It was really inspiring for me to read this as I am also with java/j2ee background. i jus wanted to ask about your education background as i am really worried on tat part. i am a simple EC graduate from a B grade collg from India. i know for me getting into google is not gonna b easy , as rght now i m jus 3+ yrs old in this IT world. Any suggestions how should i build my profile going forward so that I can think of getting into google 10yrs down the line , will be really appreciated.
- deepa02.ag December 22, 2010Thanks,
Deepa