diff options
| -rw-r--r-- | notes.md | 78 |
1 files changed, 76 insertions, 2 deletions
@@ -877,8 +877,7 @@ Big omega notation. _()_ once `n` gets large enough, the running time is at least `k1*n` and at most `k2*n` for some constants `k1` and `k2`. * we don't have to worry about which time units we're using. - * when we use big-𝚯 notation, we're saying that we have an *asymptotically - tight bound* on the running time. + * when we use big-𝚯 notation, we're saying that we have an *asymptotically tight bound* on the running time. * `𝚯(1)`: Constant time. * `𝚯(log n)`: * `𝚯(n)`: @@ -889,3 +888,78 @@ Big omega notation. _()_ * `𝚯(2^n)`: * `𝚯(n!)`: * rate of growth + + +Abdul Bari https://www.youtube.com/watch?v=A03oI0znAoc +Asymptotic Notations Big Oh - Omega - Theta + +Representing a simple form of a function + +We need a simple method for representing time complexity. + +| symbol | english | use | +| -------- | --- | --- | +| O | big-oh | upper bound of a function | +| 𝚯 | theta notation | average bound of a function | +| _()_ | big-omega | lower bound of a function | + +Theta is useful. + +1 < logn < sqrt(n) < n < nlogn < n^2 < n^3 ... < 2^n < 3^n ... < n^n + +Big-oh +------ + +The function `f(n)=O(g(n))` if there exist poitive constants c and n0 +such that `f(n) <= c * g(n) V n >= n0` + +Example: + +``` + f(n) = 2n+3 + 2n+3 <= __ 10n __ n>=1 + f(n) c*g(n) + f(n) = O(n) + + 2n+3 <= 2n+3n will always work. +``` + +instead of guessing the value you can make it as 2n+3 + + +Omega +---- + +The function `f(n) = omega(g(n)) if positive contstants c and n0` +such that `f(n) >= c * g(n) V n>=n0` + +e.g. + +``` +f(n) = 2n+3 +f(n) c * g(n) + +2n+3 >= log n V n>=1 +f(n) c * g(n) + + + true f(n) = omega(n) (most useful answer) + true f(n) = omega(logn) +``` + +Theta +----- + +The funciton `f(n)=theta(g(n)) if 3 +ve constants c1,c2 and n0` +such that `c1*g(n) <= f(n) <= c2*g(n)` + +f(n) = theta(n) + +``` +eg. +f(n) = 2n + 3 +1*n <= 2n + 3 <= 5xn +c*g(n) f(n) +``` + + |