MathCom_Algorithm_CrowthOfFunction-Summeries

Big-O notation : 

f(n) = O[g(n)] { f(n) เป็น Big-O ของ g(n) }

|f(n)| <= c×|g(n)| เมื่อ n >=k

ถ้า f(n) เป็นบวกทุก n

นั้นสามารถเขียน f(n) <= c×g(n) เมื่อ n >=k

Ex: f(n)=An³+Bn²+Cn+D = O(n³) ?

An³+Bn²+Cn+D <= c×n³ เมื่อ n >=k

An³+Bn²+Cn+D <= An³+Bn³+Cn³+Dn³ เมื่อ n >= 1 

An³+Bn²+Cn+D <= (A+B+C+D)n³ เมื่อ n >= 1

==> c = (A+B+C+D) ; k = 1

So : f(n) = O(n³)

Note : A(n^z)+........ = O(n^m) <=> m >= z 

{หมายความว่า ถ้า A(n^z)+........Big-O ของ n^m ต่อเมื่่อ m >= z   }

Comparision of Big-O {การเปลียบเทียบของBig-O}

{ O(1) <= O(log n) <= O(n) <= O(n×log n) <= O(n²) <= O(n^k) <= O(2^n) }

Summation , Multiply of Function with Big-O {การคูณและบวก}

f1(n) = O(g1(n)) and f2(n) = O(g2(n)) ==> f1(n)+f2(n) = O(max{g1(n),g2(n)}) 

f1(n) = O(g1(n)) and f2(n) = O(g2(n)) ==> f1(n)×f2(n) = O({g1(n)×g2(n)})