we investigate more theoretical method. To show that f(n) O(n), we want to find c such...

 

Transcribed Image Text:

we investigate more theoretical method. To show that f(n) O(n), we want to find c such that f(n) cg(n) (for n is eventually large). To do this, we replace each term in f(n) by the dominant terms together with some relevant constant k. The choice of k is simply the sum of coefficients of all terms in f. For example, we want to prove 2n + 5 O(n). We replace 5 by 5n and so 2n +5 2n + 5n7n. By choosing c = 7, we have 2n + 5 O(n). We explain more details as below. Show that 2n + 5 O(n). we investigate more theoretical method. To show that f(n) O(n), we want to find c such that f(n) cg(n) (for n is eventually large). To do this, we replace each term in f(n) by the dominant terms together with some relevant constant k. The choice of k is simply the sum of coefficients of all terms in f. For example, we want to prove 2n + 5 O(n). We replace 5 by 5n and so 2n +5 2n + 5n7n. By choosing c = 7, we have 2n + 5 O(n). We explain more details as below. Show that 2n + 5 O(n).