Analysis of Algo

Analysis of Algo

#https://en.wikipedia.org/wiki/Analysis_of_algorithms 
 
 The rate at which  the	running	time increases as a function of	input	is	called	rate	of	growth
 
 Worst	case 
 ○ Defines	the	input	for	which	the	algorithm	takes	a	long	time	(slowest time	to	complete). 
 ○ Input	is	the	one	for	which	the	algorithm	runs	the	slowest.
 ○ Big O notation is a convenient way to express the worst-case scenario for a given algorithm
 
 Best	case 
 ○ Defines	the	input	for	which	the	algorithm	takes	the	least	time	(fastest time	to	complete). 
 ○ Input	is	the	one	for	which	the	algorithm	runs	the	fastest. 
 ○ Omega notation is a convenient way to express the worst-case scenario for a given algorithm
 
 Average	case
 ○ Provides	a	prediction	about	the	running	time	of	the	algorithm. 
 ○ Run	the	algorithm	many	times,	using	many	different	inputs	that	come from	some	distribution	that	generates	these	inputs,	compute	the	total running	time	(by	adding	the	individual	times),	and	divide	by	the number	of	trials. ○ Assumes	that	the	input	is	random.
 
 
Asymptotic	Notation
Having	the	expressions	for	the	best,	average	and	worst	cases,	for	all	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.	
Let	us	assume	that	the	given algorithm	is	represented	in	the	form	of	function	f(n).




Big-O	Notation
This	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).

	f(n)	=	n4	+	100n2	+	10n	+	50	is	the	given	algorithm,	then	n4	is	g(n).	
  That	means g(n)	gives	the	maximum	rate	of	growth	for	f(n)	at	larger	values	of	n.
  
  O–notation	defined	as	O(g(n))	=	{f(n):	there exist	positive	constants	c	and	n0	such	that	0	≤	f(n)	≤	cg(n)	for	all	n	≥	n0}.	g(n)	is	an	asymptotic tight	upper	bound	for	f(n).	
  Our	objective	is	to	give	the	smallest	rate	of	growth	g(n)	which	is greater	than	or	equal	to	the	given	algorithms’	rate	of	growth	f(n).
  
  
  
Omega-Ω	Notation
Similar	to	the	O	discussion,	this	notation	gives	the	tighter	lower	bound	of	the	given	algorithm	and we	represent	it	as	f(n)	=	Ω(g(n)).	
That	means,	at	larger	values	of	n,	the	tighter	lower	bound	of f(n)	is	g(n)

if	f(n)	=	100n2	+	10n	+	50,	g(n)	is	Ω(n2). The	Ω	notation	can	be	defined	as	Ω(g(n))	=	{f(n):	there	exist	positive	constants	c	and	n0	such	that 0	≤	cg(n)	≤	f(n)	for	all	n	≥	n0}.	g(n)	is	an	asymptotic	tight	lower	bound	for	f(n).	
Our	objective	is to	give	the	largest	rate	of	growth	g(n)	which	is	less	than	or	equal	to	the	given	algorithm’s	rate	of growth	f(n).

Theta-Θ Notation

This notation decides whether the upper and lower bounds of a given function (algorithm) are the
same. The average running time of an algorithm is always between the lower bound and the upper
bound. If the upper bound (O) and lower bound (Ω) give the same result, then the Θ notation will
also have the same rate of growth. As an example, let us assume that f(n) = 10n + n is the
expression. Then, its tight upper bound g(n) is O(n). The rate of growth in the best case is g(n) =O(n).
It is defined as Θ(g(n)) = {f(n): there exist positive
constants c1
, c2 and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}. g(n) is an asymptotic
tight bound for f(n). Θ(g(n)) is the set of functions with the same order of growth as g(n).


for a function f(n), g(n) is an upper bound (big O) if for "big enough n", f(n)<=c*g(n), for a constant c. [g dominates f] 
g(n) is lower bound (big Omega) if for "big enough n", f(n) >= c*g(n), for a constant c. [f dominates g]

If g(n) is both upper bound and lower bound of f(n) [with different c's], we say g(n) is a tight bound for f(n) [Big theta]