Array

• Dense list (consecutive memory address)
• Pros:
  • Direct access, $O(1)$
• Cons:
  • High overhead when insertion / detetion frequently happened.

Deletion without shift

• Insertion: $O(n)$, not changed.
• Deletion: $O(n) \rightarrow O(1)$
• NO MORE direct access. Need to calculate specific index from head address.

Polynomials

多項式求值

• $p(x) = a_nx^n + a_{n-1}x^{n-1} + ...+ a_1x + a_0$
  • $O(n^2)$
• Horner's Rule
  • $p(x) = (...(a_nx + a_{n-1})x + ...+ a_1)x + a_0$
  • $O(n)$
  • More efficeint