1. Cost of operations and measuring efficiency

---

1.1. Analysing Costs

1.1.1. How to determine the costs of a program?

• Focus
  • Time
    • Run the program and count the milliseconds/minutes/days
    • Count the number of steps/operations the algorithm will take
  • Space
    • Measure the amount of memory the program occupies
    • Count the number of elementary data items the algorithm stores
• Method
  • Programs
    • Benchmarking
  • Algorithms
    • Analysis

1.2. Benchmarking: program cost

1.2.1. Measure

• Actual programs
• On real machines
• On specific input
• Measure elapsed time
  • System.currentTimeMillis() → time from system clock in milliseconds (long)
• Measure real memory usage

1.2.2. Problems

• What input
  • ⇒ choose test sets carefully use large data sets don’t include user input
• Other users/processes
  • ⇒ minimise average over many runs
• Which computer?
  • ⇒ specify details

1.3. Analysis Algorithm【 See ：INT 102_LEC 02】

1.3.1. Algorithm Complexity & Asymptotic Notation

• Abstract away from the details of
  • The hardware
  • The operating system
  • The programming language
  • The compiler
  • The program
  • The specific input
• Measure number of “steps” as a function of the data size
  • Worst case                         (easier)
  • Average case                     (harder)
  • Best case                           (easy, but useless)
• Construct an expression for the number of steps
  • Simplified into terms of different powers/functions of n
  • e.g.
    • 
    • 
• Drop the lower order terms (the ones that will be insignificant with large n)
  • e.g.
    • 
    • 
• Actual constant will depend on the hardware ⇒ Drop the constant factors
  • e.g.
    • 
    • 
• “Asymptotic cost”, or “big-O” cost
  • Describes how cost grows with input size
  • e.g.
    • 
    • 

1.3.3. Big Oh Notation

• Definition
  • A notation for describing efficiency of computer algorithms
• Example
  • Provide
    • Assuming a 100-MHz clock, 
  • Info
    • Hz : How many times in 1 second
    • 100 MHz =  Hz →   Time /s → 1 Time consumption =  =  s = 10 ns
  • Time
    • 
      • 
      • 
    • ​​​​​​​
      • 
      • 
    • ​​​​​​​
      • 
      • 
    • 
      • 
      • 
    • 
      • 
      • 
    • 
      • 
      • 
    • 
      • 
      • 

1.3.4. Typical Costs in Big ‘O’

• If data/input is size n,and has a 100-MHz clock		How does it grow
  	Constant	cost is independent of n
  	Logarithmic	size x 10 → add a little (log(10)) to the cost
  	Linear	size x 10 → 10 x the cost
  	N Log N	size x 10 → bit more than 10 x
  	Quadratic	size x 10 → 100 x the cost
  	Cubic	size x 10 → 1000 x the cost
  	Exponential	adding one to size -> doubles the cost => You don’t want to run this algorithm!
  	Fartorial	adding one to size -> n x the cost => You definitely don’t want this algorithm!

1.3.5. Common size arrangement

• 
• 

1.4. Step

1.4.1. Problem: What is a “step”?

• Count
  • Actions in the innermost loop                                (happen the most times)
  • Actions that happen every time round                   (not inside an “if”)
  • Actions involving “data values”                              (rather than indexes)
  • Representative actions                                          (don’t need every action)
• Example
  • ​​​​​​​​​​​​​​

1.4.2. What’s a step: Pragmatics

• Count the most expensive actions
  • Adding 2 numbers is cheap
  • Raising to a power is not so cheap
  • Comparing 2 strings may be expensive
  • Reading a line from a file may be very expensive
  • Waiting for input from a user or another program may take forever
• Sometimes we need to know how the underlying operations are implemented in the computer to analyse well

2. ArrayList: retrieve, remove, add​​​​​​​

2.1. ArrayList: retrieve, remove, add

2.1.1. ArrayList: get, set

• Assume List contains n items
  • Best, worst, average: 
  • Constant number of steps, regardless of n

2.1.2. ArrayList: remove

• Assume List contains n items
• Worst Case
  • Index = 0

2.1.3. ArrayList: add

• Assume List contains n items
• Worst Case
  • Index = 0
• Average case
  • O(n)

2.1.4. ArrayList: add at end

• Assume List contains n items
• Worst Case
  • Index = 0
• Average case
  • Average over all possible states and input
    • O(1)
  • Amortised cost over time
    • Total cost of adding n items / n
    • O(1)

2.1.5. Summary

• get	O(1)	Best, worst, average Constant number of steps, regardless of n
  set	O(1)
  remove	O(n)
  add(at i)	O(n)	Worst and average
  add(at end)	O(1)	Average
  	O(n)	Worst
  	O(1)	Amortised average

---

3. ArraySet: contains, remove, add

---

3.1. Cost of ArraySet

3.1.1. ArraySet uses same data structure as ArrayList

• Does not need to keep items in order

3.1.2. Operations​​​​​​​

• dcontains(item)
• add(item) ← always add at the end
• remove(item) ← don’t need to shift down – just move last item down

3.1.3. What are the costs?

• contains:             O(n)
• remove:              O(1) O(n)
• add:                    O(1) O(n)

---

4. Q & A

---

• When analysing the cost of an algorithm, loop usually is the focus. (T or F) 
  • T
• Which of the following operations is more expensive? 
  • Reading a line from a file                                  【×】
  • Reading a line from a user                                【√】
• Worst case cost analysis is usually more difficult than average cost analysis. (T or F)
  • ​​​​​​​​​​​​​​F