Big Oh notation

• We’re typically interested in the “tightest” bound we can obtain on an algorithm’s runtime complexity (the Theta bound)

• E.g., TB(n) = c3 . n

  ==> Tb(n) = O(n2) as well, but we’re more
  
  interested in the bound Tb(n) = O(n)

Previous slide

Next slide

Back to first slide

View graphic version