BIG-O, Omega and Theta notations in algorithms
Having the expression for the best, average and worst cases, for all the three cases we need to identify the upper and lower bounds. To represent these upper and lower bounds we need some kind of syntax and that is the subject of the following discussion about different notations. Let us assume that the given algorithm is represented in the form of function f(n). Big-O Notation: Big-O Notation gives the tight upper bound of the given function. Generally, it is represented as f(n)=O(g(n)). That means, at larger values of n, the upper bound of f(n) is g(n). For example, f(n) = n 4 + 100n 2 + 10n + 50 is the given algorithm, then n 4 is g(n). That means g(n) gives the maximum rate of growth for f(n) at larger values of n. Let us see the O-notation with little more details. O- notation defined as O(g(n))={f(n): there exists positive constants c and n 0 }. g(n) is an asymptotic tight upper bound for f(n). Our objective is to give smallest rate of growth g(n...