summaryrefslogtreecommitdiffhomepage
path: root/asymptotic-notation.html.markdown
diff options
context:
space:
mode:
authorLuis Custodio <luis.custodio@gmail.com>2015-10-17 13:11:25 +0200
committerLuis Custodio <luis.custodio@gmail.com>2015-10-17 13:11:25 +0200
commitf5873b08901bfaec3fb46518258ff9e886fd04c4 (patch)
tree62886b71c7226f0c6c4f979d61ff96c839a641a9 /asymptotic-notation.html.markdown
parentc9348e5a82b639093f8f3eee955ffdf6fb99b5d8 (diff)
parent0e6d9f6fe9aeffc64c3adad3e4a0ee1cc0d1dd88 (diff)
Merge branch 'master' of github.com:adambard/learnxinyminutes-docs
Diffstat (limited to 'asymptotic-notation.html.markdown')
-rw-r--r--asymptotic-notation.html.markdown26
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