diff options
| author | Lari Kovanen <lari@kovanen.se> | 2015-12-09 13:25:01 +0100 | 
|---|---|---|
| committer | Lari Kovanen <lari@kovanen.se> | 2015-12-09 13:25:01 +0100 | 
| commit | 46d3c28a5fc341f3b8ef061e963adfc7c610263e (patch) | |
| tree | 794df6f192a3875dc09d2710395048c5f405a806 /asymptotic-notation.html.markdown | |
| parent | dbfb19bb5779e84add18a19ebc36833e748e69d9 (diff) | |
| parent | 1f76b2ad8c35b6c7e8ac2cc5dac8f20bc74f09ef (diff) | |
Merge remote-tracking branch 'adambard/master'
Diffstat (limited to 'asymptotic-notation.html.markdown')
| -rw-r--r-- | asymptotic-notation.html.markdown | 26 | 
1 files changed, 13 insertions, 13 deletions
| diff --git a/asymptotic-notation.html.markdown b/asymptotic-notation.html.markdown index e1f961f8..a516737e 100644 --- a/asymptotic-notation.html.markdown +++ b/asymptotic-notation.html.markdown @@ -72,45 +72,45 @@ for a given function. Say `f(n)` is your algorithm runtime, and `g(n)` is an arb  you are trying to relate to your algorithm. `f(n)` is O(g(n)), if for any real constant c (c > 0),  `f(n)` <= `c g(n)` for every input size n (n > 0). -*Example 1*   +*Example 1*  ``` -f(n) = 3log n + 100   +f(n) = 3log n + 100  g(n) = log n  ``` -Is `f(n)` O(g(n))?   -Is `3 log n + 100` O(log n)?   +Is `f(n)` O(g(n))? +Is `3 log n + 100` O(log n)?  Let's look to the definition of Big-O.  ``` -3log n + 100 <= c * log n   +3log n + 100 <= c * log n  ``` -Is there some constant c that satisfies this for all n?   +Is there some constant c that satisfies this for all n?  ``` -3log n + 100 <= 150 * log n, n > 2 (undefined at n = 1)   +3log n + 100 <= 150 * log n, n > 2 (undefined at n = 1)  ```  Yes! The definition of Big-O has been met therefore `f(n)` is O(g(n)). -*Example 2*   +*Example 2*  ``` -f(n) = 3*n^2   +f(n) = 3*n^2  g(n) = n  ``` -Is `f(n)` O(g(n))?   -Is `3 * n^2` O(n)?   +Is `f(n)` O(g(n))? +Is `3 * n^2` O(n)?  Let's look at the definition of Big-O.  ``` -3 * n^2 <= c * n   +3 * n^2 <= c * n  ``` -Is there some constant c that satisfies this for all n?   +Is there some constant c that satisfies this for all n?  No, there isn't. `f(n)` is NOT O(g(n)).  ### Big-Omega | 
