diff options
author | Jake Prather <JakeHP@Zoho.com> | 2015-02-01 11:13:22 -0600 |
---|---|---|
committer | Jake Prather <JakeHP@Zoho.com> | 2015-02-01 11:13:22 -0600 |
commit | 4380245292e64ca22cd5cc6927ac146815914681 (patch) | |
tree | 44c6fb42ba6915a53291e26943bf57a6f2aeb7ab /asymptotic-notation.html.markdown | |
parent | ef57fcd9a83e171144abb3bdd8b9a3f88c12d2ee (diff) |
formatting
Diffstat (limited to 'asymptotic-notation.html.markdown')
-rw-r--r-- | asymptotic-notation.html.markdown | 34 |
1 files changed, 19 insertions, 15 deletions
diff --git a/asymptotic-notation.html.markdown b/asymptotic-notation.html.markdown index ea23b19a..ba665a95 100644 --- a/asymptotic-notation.html.markdown +++ b/asymptotic-notation.html.markdown @@ -76,27 +76,31 @@ for a given function. Say f(n) is your algorithm runtime, and g(n) is an arbitra 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 -f(n) = 3log n + 100 +*Example 1* +``` +f(n) = 3log n + 100 g(n) = log n +``` -is f(n) O(g(n))? -is 3 log n + 100 O(log n)? -Let's look to the definition of Big-Oh. -3log n + 100 <= c * log n -Is there some constant c that satisfies this for all n? -3log n + 100 <= 150 * log n, n > 2 (undefined at n = 1) +is f(n) O(g(n))? +is 3 log n + 100 O(log n)? +Let's look to the definition of Big-Oh. +3log n + 100 <= c * log n +Is there some constant c that satisfies this for all n? +3log n + 100 <= 150 * log n, n > 2 (undefined at n = 1) Yes! The definition of Big-Oh has been met therefore f(n) is O(g(n)). -Example 2 -f(n) = 3*n^2 +*Example 2* +``` +f(n) = 3*n^2 g(n) = n +``` -is f(n) O(g(n))? -is 3*n^2 O(n)? -Let's look at the definition of Big-Oh. -3*n^2 <= c * n -Is there some constant c that satisfies this for all n? +is f(n) O(g(n))? +is 3*n^2 O(n)? +Let's look at the definition of Big-Oh. +3*n^2 <= c * 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 |