Big O notation

I am preparing for interviews. These are the points that I extracted from Analyzing Algorithm Performance about big O notation.

• When we say that one algorithm is more efficient than another one it means that is uses less resource.

• By resource we mean CPU cycles and Computer Memory; however due to the fact that the price of computer memory is constantly decreasing, it mostly refers to the CPU Cycles or the duration of the execution

• The other important concern is with significant differences in efficiency

• Since we are only interested in significant differences between algorithms, we can ignore everything except the dominant terms and express the algorithm growth function in terms of the order of magnitude of the growth rate or O(N)

• This allows the analyst to ignore computer/compiler/coding tricks. When evaluating an algorithm and focus on the general behavior of the algorithm.

• O(1) time to perform the algorithm is constant and does not depend on the size of the problem

• O(log2N) time requirement is logarithmic

• O(N) time requirement is linear

• O(Nlog2N) is N logarithmic (N logarithmic growth rate)

• O(N2) time requirement is quadratic (quadratic growth rate)

• O(N3) time requirement is cubic (cubic growth rate)

• O(2N) time requirement is exponential (exponential growth rate)

• The performance of many algorithms is based on the data there are three cases we consider (Base case, average case, and worst case)

 // Sequential search = O(N) int find1(int n, char array[MAX_STR][MAX_LEN],char key[MAX_LEN]) {    int i;     for(i=0;i<>

 //O(log2 N) int find2(int n, char array[MAX_STR][MAX_LEN],char key[MAX_LEN]) {    int low  = 0;    int high = n-1;    int mid;     int outcome;     while( low <= high )    {       mid = (low+high) / 2;       outcome = strcmp(array[mid],key);       if( outcome==0 )     return(mid);       else if( outcome < low =" mid+1;"> 0 )     high = mid-1;    }     return(-1); }