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