0

1.4kviews

Write short note on growth of functions.

written 2.1 years ago by | • modified 2.1 years ago |

Write short note on growth of functions.

ADD COMMENT
EDIT

**1 Answer**

0

1.4kviews

Write short note on growth of functions.

written 2.1 years ago by | • modified 2.1 years ago |

Write short note on growth of functions.

ADD COMMENT
EDIT

0

106views

written 2.1 years ago by |

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.

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’.

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.

- 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).

- σ-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).

ADD COMMENT
EDIT

Please log in to add an answer.