[reuben_tate]

Also, simply memorizing the time efficiencies of common algorithms may not be good enough, you should be able to look at the code yourself and do some analysis to determine the Big-O yourself. Your interviewer may hand you some code and ask you what the worst case time efficiency is.

These are from a simple review quiz I had on my first day of class. If you can do these you should be fine.

Find the Big-O of the following functions / code fragments

static long Fibonacci(int n) {
    if (n==1||n==2) return 1;
    return Fibonacci(n-2)+Fibonacci(n-1);
}

O(2^n)

for (int i=0,j=0; i<n; i++)
    for (double d=1; d<n; d*=2)
        j++;

O(n*logn)

int[] a=new int[n];
for (int i=4;i<n;i++) {
    for (int j=i-3,sum=a[i-4];j<=i;j++)
        sum+=a[j];
}

O(n)

private static long gcd(long n,long r) {
    if (r==0) return n;
    return gcd(r,n%r);
}

O(log(n))