## Searching

- O(1) vs O(n)
- key-based search
- ordered vs. unordered
- internal searches (memory) vs. external searches (files)
- algorithms
- sequential search O(n)
- binary search O(log n) - sorted data

## adding/deleting from array

for I = 1 to N - 1 do
A[I -1] = A[I];

## To reorder an array after deletion:

- O(N*N-1) > O(N)
- O(N*(N/2)) > O(N)

## "Statistical" or "Probabilistic" Reordering

- Move to front
- Transposition

## Ordered linked list insert/delete = O(N/2)

Return to CIS 350 Index Page