CPT 102_LEC 16

1. Cost of ArraySet operations

1.1. ArrayList costs

• Get	O (1)
  Set	O (1)
  Remove	O (n)
  Add (at i)	O (n)	worst & average
  Add (at end)	O (1)	most of the time
  	O (n)	worst
  	O (1)	amortised average

1.2. ArraySet costs

1.2.1. Features

• Order is not significant
  • ⇒ add() can choose to put a new item anywhere
  • ⇒ can reorder when removing an item
• Duplicates not allowed
  • ⇒ must check if item already present before adding

1.2.2. Algorithms

• Contains(value)

  • search through array, 
        if value equals item
            return true
    return false

• Add(value)

  • if not contains(value),
        place value at end, (doubling array if necessary)
        increment size

• Remove(value)

  • search through array
        if value equals item
            replace item by item at end. (why?)
            decrement size
            return

2. Binary Search

见INT 102 LEC_03 的 1.2 Binary Search

3. Cost of SortedArraySet with Binary Search

•