diff options
author | Cameron Schermerhorn <Cameron.Schermerhorn@its.ny.gov> | 2015-10-09 13:30:07 -0400 |
---|---|---|
committer | Cameron Schermerhorn <Cameron.Schermerhorn@its.ny.gov> | 2015-10-09 13:30:07 -0400 |
commit | d2010c08604c25b3166977e0cde795732ecde551 (patch) | |
tree | d4d6d72b9364e85decc55770e1f451f479321b67 /asymptotic-notation.html.markdown | |
parent | bf7d33037f64ea9f80f106a37929e3fdf20bd24d (diff) | |
parent | ea943b61fbee8fb0ba34f88b4d0380400e890f30 (diff) |
Merge remote-tracking branch 'refs/remotes/adambard/master'
Conflicts:
java.html.markdown
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 |