Short Notes Of Algorithm
Analyze an algorithm 1) Worst Case Analysis (Usually Done ):In the worst case analysis, we calculate upper bound on running time of an algorithm by considering worst case (a situation where algorithm takes maximum time) 2 ) Average Case Analysis (Sometimes done ) :In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. 3) Best Case Analysis (Bogus ) :In the best case analysis, we calculate lower bound on running time of an algorithm. Asymptotic Notations Θ Notation: The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior. Θ((g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0} Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above. O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= cg(n) for all n >= n0} Ω Nota