Analyzing algorithms

---

1. random-access machine (RAM)

• algorithm analyzing의 배경이 되는 implementation technology와 resources등의 model 중 하나
• instructions는 하나씩만 실행 가능하고 concurrent operations는 불가능
• real computers에 존재하는 대부분의 instructions(arithmetic, data movement, control)를 갖고 있다
• data types는 integer와 floating point가 있다
• memory-hierarchy(caches or virtual memory) effects를 고려하지 않는다

Analysis of insertion sort

1. input size

• 많은 problems에서, 가장 natural measure는 input의 items 갯수
• ordinary binary notation으로 표현하기 위해 필요한 total number of bits인 경우도 존재

2. running time

• the number of primitive operations or "steps" executed
• step의 개념은 machine에 독립적으로 만든다
• $i$th line은 $c_i$만큼의 시간이 걸린다고 가정

3. running time of INSERTION-SORT

• the running time of the algorithm = the sum of running times for each statement executed

• $T(n)$ = the running time of INSERTION-SORT on an input of $n$ values
  

• the best case

  • the best case occurs if the array is already sorted
    
  • we can express this running time as $an+b$ (linear function)

• the worst case

  • if the array is in reverse sorted order, the worst case results
    
    
  • we can express this worst-case running time as $an^2+bn+c$ (quadratic function)

Worst-case and average-case analysis

1. three reasons for concentrating on finding only the worst-case running time

• The worst-case running time of an algorithm gives us an upper bound on the running time for any input
• For some algorithms, the worst case occurs fairly often
• The "average case" is often roughly as bad as the worst case

Order of growth

1. abstractions

• Using the constants $c_i$ to represent costs
• Expressing the worst-case running time as $an^2+bn+c$ for some constants $a$, $b$, and $c$ that depend on the statement costs $c_i$

2. more simplifying abstraction

• the rate of growth, or order of growth
• considering only the leading term of a formula ($e.g., an^2$)
• ignoring the leading term's constant coefficient
• insertion sort has a worst-case running time of $\theta(n^2)$