summaryrefslogtreecommitdiffhomepage
path: root/asymptotic-notation.html.markdown
diff options
context:
space:
mode:
authorJake Prather <JakeHP@Zoho.com>2015-02-01 11:13:22 -0600
committerJake Prather <JakeHP@Zoho.com>2015-02-01 11:13:22 -0600
commit4380245292e64ca22cd5cc6927ac146815914681 (patch)
tree44c6fb42ba6915a53291e26943bf57a6f2aeb7ab /asymptotic-notation.html.markdown
parentef57fcd9a83e171144abb3bdd8b9a3f88c12d2ee (diff)
formatting
Diffstat (limited to 'asymptotic-notation.html.markdown')
-rw-r--r--asymptotic-notation.html.markdown34
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