Some notes on algorithm analysis

alogrithm_analysis

asymptotic analysis(mathematical formalization)
- Basic vocabulary to discuss design and analysis of algorithms
- focuses on the "sweet spot" to suppress architecture/language/compiler dependent details.
- sharp enough to make useful comparisons between different alogrithms, especially on large inputs.
- suppress constant factors and lower-order terms.
- lower order terms are irrelevant for large inputs, constant factors are too system dependent.

Example: One loop
Problem: Does array A contain the integer t?
 given A (array of length n)
 and t(and integer)

for(i=1 to n){
  if(A[i] == t) return TRUE;
  else return FALSE;
}

what is the running time? Q: O(n)


Example: Two Loops
given A, B(arrays of length n)
and t (an integer)

for(i=1 to n)
  if(A[i] == t) return TRUE;
for(i=1 to n)
  if(B[i] == t) return TRUE;
return FALSE;

Question: running time? A: O(n)

Example: Two nested Loops
Problem: do arrays A, B have a number in common?
given arrays A,B of length n

for i=1 to n
  for j=1 to n 
      if A[i] == B[j] return TRUE
return FALSE

Question:running time? A: O(n2) , a quadratic algorithm