UBC Wiki - User contributions [en]

User:Niels

2010-02-02T02:38:54Z

Niels: Created page with '=== Niels is Cool! === Currently a CPSC student in Course:CPSC 320 with Steve Wolfman.'

=== Niels is Cool! ===

Currently a CPSC student in [[Course:CPSC 320]] with Steve Wolfman.

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T02:28:28Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Analogy to Inequalities ===

* <math> f(n) = O(g(n))</math> if and only if <math>g(n) = \Omega(f(n))</math>
* <math> f(n) = o(g(n))</math> if and only if <math>g(n) = \omega(f(n))</math>

It follows, where <math>a \rightarrow f(n)</math> and <math>b \rightarrow g(n)</math>:

* <math> f(n) = O(g(n)) \approx a \leq b</math>
* <math> f(n) = \Omega(g(n)) \approx a \geq b</math>
* <math> f(n) = \Theta(g(n)) \approx a = b</math>
* <math> f(n) = o(g(n)) \approx a < b</math>
* <math> f(n) = \omega(g(n)) \approx a > b</math>

Caution: For all <math>a, b, \in \mathbf{R}</math> exactly one must hold: <math> a<b, a=b</math> or <math> a>b </math>. Not all functions are asymptotically comparable.

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
<math> \frac{d}{dx} a^{f(x)} = a^{f(x)} * \frac{d(f(x))}{dx} ln(a) </math>

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T02:27:22Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Analogy to Inequalities ===

* <math> f(n) = O(g(n))</math> if and only if <math>g(n) = \Omega(f(n))</math>
* <math> f(n) = o(g(n))</math> if and only if <math>g(n) = \omega(f(n))</math>

It follows, where <math>a \rightarrow f(n)</math> and <math>b \rightarrow g(n)</math>:

* <math> f(n) = O(g(n)) \approx a \leq b</math>
* <math> f(n) = \Omega(g(n)) \approx a \geq b</math>
* <math> f(n) = \Theta(g(n)) \approx a = b</math>
* <math> f(n) = o(g(n)) \approx a < b</math>
* <math> f(n) = \omega(g(n)) \approx a > b</math>

Caution: For all <math>a, b, \in \mathbf{R}</math> exactly one must hold: <math> a<b, a=b</math> or <math> a>b </math>. Not all functions are asymptotically comparable.

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
<math> \frac{d}{dx} a^{f(x)} = a^{f(x)} * \frac{d(f(x))}{dx} ln(a) </math>

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T02:20:21Z

Niels: /* Derivatives */

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Analogy to Inequalities ===

* <math> f(n) = O(g(n))</math> if and only if <math>g(n) = \Omega(f(n))</math>
* <math> f(n) = o(g(n))</math> if and only if <math>g(n) = \omega(f(n))</math>

It follows, where <math>a \rightarrow f(n)</math> and <math>b \rightarrow g(n)</math>:

* <math> f(n) = O(g(n)) \approx a \leq b</math>
* <math> f(n) = \Omega(g(n)) \approx a \geq b</math>
* <math> f(n) = \Theta(g(n)) \approx a = b</math>
* <math> f(n) = o(g(n)) \approx a < b</math>
* <math> f(n) = \omega(g(n)) \approx a > b</math>

Caution: For all <math>a, b, \in \mathbf{R}</math> exactly one must hold: <math> a<b, a=b</math> or <math> a>b </math>. Not all functions are asymptotically comparable.

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
<math> d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a) </math>

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T02:19:44Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Analogy to Inequalities ===

* <math> f(n) = O(g(n))</math> if and only if <math>g(n) = \Omega(f(n))</math>
* <math> f(n) = o(g(n))</math> if and only if <math>g(n) = \omega(f(n))</math>

It follows, where <math>a \rightarrow f(n)</math> and <math>b \rightarrow g(n)</math>:

* <math> f(n) = O(g(n)) \approx a \leq b</math>
* <math> f(n) = \Omega(g(n)) \approx a \geq b</math>
* <math> f(n) = \Theta(g(n)) \approx a = b</math>
* <math> f(n) = o(g(n)) \approx a < b</math>
* <math> f(n) = \omega(g(n)) \approx a > b</math>

Caution: For all <math>a, b, \in \mathbf{R}</math> exactly one must hold: <math> a<b, a=b</math> or <math> a>b </math>. Not all functions are asymptotically comparable.

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T02:17:24Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Analogy to Inequalities ===

* <math> f(n) = O(g(n))</math> if and only if <math>g(n) = \Omega(f(n))</math>
* <math> f(n) = o(g(n))</math> if and only if <math>g(n) = \omega(f(n))</math>

It follows, where <math>a \approx f(n)</math> and <math>b \approx f(n)</math>:

* <math> f(n) = O(g(n)) \approx a \leq b</math>
* <math> f(n) = \Omega(g(n)) \approx a \geq b</math>
* <math> f(n) = \Theta(g(n)) \approx a = b</math>
* <math> f(n) = o(g(n)) \approx a < b</math>
* <math> f(n) = \omega(g(n)) \approx a > b</math>

Caution: For all <math>a, b, \in \mathbf{R}</math> exactly one must hold: <math> a<b, a=b</math> or <math> a>b </math>. Not all functions are asymptotically comparable.

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T02:15:52Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Analogy to Inequalities ===

* <math> f(n) = O(g(n)) if and only if g(n) = \Omega(f(n))</math>
* <math> f(n) = o(g(n)) if and only if g(n) = \omega(f(n))</math>

It follows, where <math>a \approx f(n)</math> and <math>b \approx f(n)</math>:

* <math> f(n) = O(g(n)) \approx a \leq b</math>
* <math> f(n) = \Omega(g(n)) \approx a \geq b</math>
* <math> f(n) = \Theta(g(n)) \approx a = b</math>
* <math> f(n) = o(g(n)) \approx a < b</math>
* <math> f(n) = \omega(g(n)) \approx a > b</math>

Caution: For all <math>a, b, \in \mathbf{R}</math> exactly one must hold: <math> a<b, a=b</math> or <math> a>b </math>. Not all functions are asymptotically comparable.

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T02:13:04Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Analogy to Inequalities ===

<math> f(n) = O(g(n)) if and only if g(n) = \Omega(f(n))</math>
<math> f(n) = o(g(n)) if and only if g(n) = \omega(f(n))</math>

It follows that:

* <math> f(n) = O(g(n)) \approx a \leq b</math>
* <math> f(n) = \Omega(g(n)) \approx a \geq b</math>
* <math> f(n) = \Theta(g(n)) \approx a = b</math>
* <math> f(n) = o(g(n)) \approx a < b</math>
* <math> f(n) = \omega(g(n)) \approx a > b</math>

Caution: For all <math>a, b, \in \mathbf{R}</math> exactly one must hold: <math> a<b, a=b</math> or <math> a>b </math>. Not all functions are asymptotically comparable.

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T01:09:42Z

Niels: /* The Silicon Downs : Furlongs of Asymptotic Complexity */

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(nlog n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T01:08:35Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(n log n)</math>
* Superlinear <math> \in O(n^{1+c})</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T01:07:59Z

Niels: /* The Silicon Downs : Furlongs of Asymptotic Complexity */

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(n log n)</math>
* Superlinear <math> \in O(n^[1+c])</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T01:04:11Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(n log n)</math>
* Superlinear <math> \in O(n^1+c)</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"

Course:CPSC 320/Midterm 1 Reference Sheet

2010-02-02T01:03:06Z

Niels:

== CPSC 320 2009W2 Exam Reference Sheet ==

'''Do not remove:''' This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

* <math>f(n) \in O(g(n))</math> iff <math>\exist c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) \leq c g(n)</math>
* <math>f(n) \in \Omega(g(n))</math> iff <math>g(n) \in O(f(n))</math>
* <math>f(n) \in \Theta(g(n))</math> iff <math>f(n) \in O(g(n))</math> and <math>g(n) \in O(f(n))</math>
* <math>f(n) \in o(g(n))</math> iff <math>\forall c \in \mathbf{R^+}, \exist n_0 \in \mathbf{Z^+}, \forall n \in \mathbf{Z^+}, n \geq n_0 \rightarrow f(n) < c g(n)</math>
* <math>f(n) \in \omega(g(n))</math> iff <math>g(n) \in o(f(n))</math>

Also, if <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} =</math>

* <math>\infty</math>, then <math>f(n) \in \omega(g(n))</math>
* a non-zero constant, then <math>f(n) \in \Theta(g(n))</math>
* <math>0</math>, then <math>f(n) \in o(g(n))</math>

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{0}{0}</math> or <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}</math>, then <math>\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{f(n)'}{g(n)'}</math>

=== Master Theorem ===
If <math>\displaystyle T(n) = aT(''n/b'') + f(n)</math> and a constant in the base case, where <math>''n/b''</math> can be either <math>\lfloor n/b \rfloor</math> or <math>\lceil n/b \rceil</math>, <math> a >= 1 </math> and <math> b > 1 </math> then:
* If <math>f(n) \in O(n^{log_b {a-\mathcal{E}}})</math> for some <math>\mathcal{E} >0</math>, then <math>T(n) \in \Theta(n^{log_b a})</math>
** Dominated by leaf cost
* If <math>f(n) \in \Theta (n^{log_b a})</math> then, <math>T(n) \in \Theta (n^{log_b a} lg n) </math>
** Balanced cost
* If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math> for some <math>\mathcal{E} > 0</math> and if <math>\displaystyle af(''n/b'') \leq cf(n)</math> for some constant <math>\displaystyle c < 1</math> and sufficiently large <math>n</math>, then <math>T(n) \in \Theta(f(n))</math>
** Dominated by root cost

The following equations cannot be solved using the master theorem:<ref>

</ref>

*:<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math> ''a'' is not a constant

*:<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math> non-polynomial difference between f(n) and <math>n^{\log_b a}</math>

*:<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math> ''a''<1 cannot have less than one sub problem

*:<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math> f(n) is not positive

*:<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math> case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If <math>f(n) \in \Omega(n^{log_b {a+\mathcal{E}}})</math>

=== Log Laws ===
For all real a > 0, b > 0, c > 0, and n,
*<math>a = b^{\log_b a}</math>
*<math>\log_c ab = \log_c a + \log_c b</math>
*<math>\log_b a^n = n \log_b a</math>
*<math>\log_b a = \frac{\log_c a}{\log_c b}</math>
*<math>\log_b \frac{1}{a} = -\log_b a</math>
*<math>\log_b a = \frac{1}{\log_a b}</math>
*<math>a^{\log_b c} = c^{\log_b a}</math>

=== Summation ===
*Arithmetic Series: <math>\displaystyle{\sum_{k=1}^n(k) = 1 + 2 + \dots + n} = \frac{1}{2}n(n + 1)</math>
*Sum of Squares: <math>\displaystyle{\sum_{k=0}^n(k^2)} = \frac{n(n+1)(2n+1)}{6}</math>
*Sum of Cubes: <math>\displaystyle{\sum_{k=0}^n(k^3)} = \frac{n^2(n+1)^2}{4}</math>
*Geometric Series: <math>\displaystyle{\sum_{k=0}^n(x^k) = 1 + x + x^2 + \dots + x^k} = \frac{x^{n + 1} - 1}{x -1 }, </math> for real <math> x \ne 1</math>
*Infinite decreasing: <math>\displaystyle{\sum_{k=0}^{\infty}(x^k) = \frac{1}{ 1 - x }, for |x| < 1 } </math>
*Telescoping: <math> \displaystyle{\sum_{k=1}^{n-1}(a_{k} - a_{k +1}) = a_0 - a_n } </math>

===Exponents===
* <math>a^0 = 1</math>
* <math>a^1 = a</math>
* <math>a^{-1} = \frac{1}{a}</math>
* <math>(a^m)^n = a^{mn}</math>
* <math>a^m \times a^n = a^{m+n}</math>

=== Decision Tree-Related Notes ===

* for a list of <math>n</math> elements, there's <math>n!</math> permutations
* a binary tree of height <math>d</math> has at most <math>2^d</math> leaves
* therefore, a binary tree with at least <math>n</math> leaves must have height at least <math>\lceil \lg n\rceil</math>
* <math>\lg(n!) \in \Theta(n \lg n)</math>, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

=== Stirling's Approximation ===

*:<math>\ln n! \sim n\ln n - n\ .</math>

=== Derivatives ===
d/dx a^f(x) = a^f(x) * d(f(x))/dx * ln(a)

=== The Silicon Downs : Furlongs of Asymptotic Complexity ===

="NEWS FLASH: Mounties Find Silicon Downs Fixed!"=
* Constant <math> \in O(1)</math>
* Logarithmic <math> \in O(log n)</math> ie. <math>log_k n , log n^2 \in O(log n)</math>
* Poly-Log <math> \in O(log^k n)</math>
* Linear <math> \in O(n)</math>
* Log-Linear <math> \in O(n log n)</math>
* Superlinear <math> \in O(n^1+c)</math> where: c is a constant > 0
* Quadratic <math> \in O(n^2)</math>
* Cubic <math> \in O(n^3)</math>
* Polynomial <math> \in O(n^k)</math> where: k is a constant, "tractable"
* Exponential <math> \in O(c^n)</math> where: c is a constant > 1, "intractable"