Asymptotic Analysis

• Running time of an algorithm is a function of the size of it's input.
• How fast does an algorithm grow with input size ? This is the rate of growth of the running time.
• Three kinds of asymptotic notation :
• Big Theta : Provides an asymptotically tight bound on the running time of an algo. If f(n) is BigTheta(g(n)) this means that f(n) grows (asymptotically) at the same rate as g(n)
• Big Omega : Provides an asymptotically lower bound on the running time of an algo. If f(n) is BigOmega(g(n)) this means that f(n) grows (asymptotically) no slower than g(n)
• Big O : Provides an asymptotically upper bound on the running time of an algo. If f(n) is O(g(n)) this means that f(n) grows (asymptotically) no faster than g(n)
• e.g. consider binary search, the worst-case running time is log(n).
• So we can say Running time of binary search i.e. f(n) - the actual algorithm logic - grows no faster than log(n) i.e. g(n). So we say BinarySearch is O(log(n)).