====== 2.2 Asymptotic Order of Growth======


===Asymptotic Upper Bounds===

   *Let T(//n//) be a function(let's assume it is the worst-case running time of a certain algorithm on an input of size //n//).
   *Given another function //f(n)//, we say that T(//n//) is O( //f(n)) (//T(//n//) is order  //f(n)//)if for sufficiently large //n//, the function T(//n//) is bounded above by a constant multiple of //f(n)//. We can write this relation as T(//n//) = O(//f(n)//). To be precise, T(//n//) is O(//f(n)//) if there exist constants //c// > 0 and //n<sub>0</sub>// >= 0 such that  for all //n// >= //n<sub>0</sub>//, we have T(//n//) ≤  //c//. The constant //c// works for all //n//,doesn't depend on //n//. In this case, we say that T is //asymptotically upper-bounded by f//. To find the upper bound //f//, we inflate the terms in the equation of T(//n//).
For instance, if T(n) = pn<sup>2</sup> + qn + r where p, q, r are positive constants, \\
For all n ≥ 1,\\
 T(n) = p//n//<sup>2</sup> + qn + r
 => T(n) ≤ pn<sup>2</sup> + qn<sup>2</sup>+ rn<sup>2</sup> \\
pn<sup>2</sup> + qn<sup>2</sup>+ rn<sup>2</sup> = (p+q+r) n<sup>2</sup> = c n<sup>2</sup>\\
=> T(n) ≤ cn<sup>2</sup>, where c = p+q+r \\
Thus, T(n) = O(n<sup>2</sup>)

===Asymptotic Lower Bounds===

  *Let T(//n//) be a function(let's assume it is the worst-case running time of a certain algorithm on an input of size //n//).
  *To show that an upper bound found the best one possible, we need to express the notion that for arbitrarily large input sizes //n//,the function T(//n//) is at least a constant multiple of some specific function //f(n)//. Thus we write T(//n//) = Ω(//f(n)//)(T(//n//) is Ω(//f(n)//)) if there exist constants if there exist constants ε > 0 and n<sub>0</sub> ≥ 0 such that for all n ≥ n<sub>0</sub> , we have T(n) ≥ ε · //f(n)//). In this case, T is //asymptotically lower-bounded by f//. the constant ε is fixed,and is independent of //n//. This time, we deflate the terms of the polynomial T instead of inflating them to find the lower bound.

For instance, if T(n) = pn<sup>2</sup> + qn + r where p, q, r are positive constants

For all n ≥ 0,
T(n) = pn<sup>2</sup> + qn + r ≥ pn<sup>2</sup>\\
=> T(n) ≥ εn<sup>2</sup>, where ε = p > 0\\

=>T(n) = Ω(n) \\

===Asymptotic Tight Bounds===

  * If we can show that a running time T(n) is both O(//f(n)//) and also Ω (//f(n)//),then we have found the //right// bound: T(//n//) grows exactly like //f(n)//to within a constant factor.
  * If a function is both  O(//f(n)//) and also Ω (//f(n)//), we say that T(//n//) is Θ(//f(n)//). In this case, we say that //f(n)// is an //asymptotically  tight bound // for T(n).
  * If we let //f// and //g// be two functions such that the limit as n tends to infinity of //f(n)// / //g(n)// exists and is equal to some number c > 0, then //f(n)// = Θ(//g(n)//).


=== Properties of Asymptotic Growth Rates===

  * Transitivity:
      *If f = O(g) and g = O(h) then f = O(h)
      *If f = Ω(g) and g = Ω(h) then f = Ω(h)
      *If f = Θ(g) and g = Θ(h) then f = Θ(h)
  *Sums of functions:
      * If f = O(h) and g = O(h) then f + g = O(h)
      * If f = Ω(h) and g = Ω(h) then f + g = Ω(h)
      * If f = Θ(h) and g = Θ(h) then f + g = Θ(h)
      * Let k be a fixed constant and let f<sub>1</sub>,f<sub>2</sub>,...,f<sub>k</sub> // and //h// be functions such that f<sub>i</sub> = O(//h//) for all //i//.\\ Then //f<sub>1</sub> + f<sub>2</sub>+...+ f<sub>k</sub> =O(//h//).\\


===Asymptotic Bounds for some Common Functions ===



  * __Polynomials__: For a polynomial T(n) = a<sub>0</sub> + a<sub>1</sub>n + … + a<sub>d</sub>n<sup>d</sup> of degree //d//, in which the coefficient a<sub>d</sub> is positive, //f// = O(n<sup>d</sup>)
  * __Logarithms__: log<sub>b</sub> n is the number //x// such that //b//<sup>//x//</sup> = //n//. If we round log<sub>b</sub>n to the nearest integer, it is one less than the number of digits in the base-b representation of the number //n//.
       * For every //b// > 1 and every //x// > 0,\\ log<sub>b</sub>n = O(n<sup>//x//</sup>).
   * Exponentials : Let //f(//n//)// = r<sup>n</sup>. For every r > 1 and every //d// > 0, //n// <sup>d</sup> = O(r<sup>n</sup>).

These three functions are the most frequent functions encountered when analyzing running times. Logarithms grow more slowly than polynomials and polynomials grow more slowly than exponentials.\\

There are several motivations for studying the bounds of the running times of algorithms. Knowing the running time of an algorithm, one can easily perfect an algorithm as much he/she can. The running times serve as a measure of comparison when searching for which algorithm is more efficient for a given problem. Thus a programmer should always aim for the most efficient algorithm he/she can possibly design and be convinced it's more efficient than that he/she had previously implemented thanks to the knowledge of the running times of algorithms.\\

I don't have a specific question about this section as most of the material makes sense. After rereading this section and seeing how it was presented in class, I can now see the importance of tight bounds. Tight bounds are a new concept for me when it comes to running times of algorithms,but I was able to see why they are useful in analyzing the algorithm: They give approximate,more precise limits to the running time of the algorithms. I would like to remember the properties of the running times of algorithms, they look very useful and I'm convinced they can help a lot in analyzing running times of algorithms.\\

This section was interesting too, I give it a 9/10.