Big Oh Examples

Example 1

T(N)  = N * (1 + 1 + 1)
      = N * 3

O(3N) = O(N)

Example 2 - Sequential Search

for I = 1 to N do
  if X = A[I] then
    begin
      print I
      stop
    end
print "done"

O(1) - best case: successful search
O(N) - worst case: successful search
O(N) - unsuccessful search

Return to CIS 350 Index Page