0
1.4kviews
Write short note on growth of functions.

Write short note on growth of functions.

1 Answer
0
106views


  1. We need to approximate the number of steps required to execute any algorithm because of the difficulty involved in expression or difficulty in evaluating an expression. We compare one function with another function to know their rate of growths.

  2. If f and g are two functions we can give the statements like ‘f has same growth rate as g’ or ‘f has higher growth rate than g’.

  3. Growth rate of function can be defined through notation.

    • θ-Notation (Same order) : This notation bounds a function to within constant factors. We say f(n) = θg(n) if there exist positive constants $n_0$, $c_1$ and $c_2$ such that to the right of $n_0$ the value of f(n) always lies between $c_1$g(n) and $c_2g(n)$ inclusive.

enter image description here


  • O-Notation (Upper bound) : This notation gives an upper bound for a function to within a constant factor. We write f(n) = O(g(n)) if there are positive constants $n_0$ and c such that to the right of $n_0$, the value of f(n) always lies on or below cg(n).

enter image description here


  • σ-Notation (Lower bound) : This notation gives a lower bound for a function to within a constant factor. We write f(n) = σg(n)) if there are positive constants $n_0$ and c such that to the right of $n_0$ , the value of f(n) always lies on or above cg(n).

enter image description here

Please log in to add an answer.