Category Archives: Algorithm & Performance

Algorithm & Performance

Posted on by
Reply

ALGORITHM & PERFORMANCE

An algorithm is a definite, step-by-step procedure for performing some task.

Algorithm is of two types :

  1. 1. Incremental algorithm – It proceeds in step incremental order.
  2. 2. Divide & conquer algorithm – It breaks the problem into several sub problems that are similar to original problem but smaller in size, solve them recursively and then combine these solutions to create a solution to the original problem.

PERFORMANCE

  • When we discuss algorithms, we often need a way of talking about the efficiency of the algorithm, that is, what sort of resources will be required to execute the algorithm.
  • The resource in question can be time how long will the algorithm run or space how much memory will the algorithm require.
  • In practice, we will mostly be concerned with the run-time efficiency of the algorithm, but many of the same ideas apply to space efficiency.

Algorithm Analysis

  • The worst-case running time, this refers to the longest running time of the algorithm for any input of size n.
  • The best-case running time, which refers to the shortest running time for any input of size n.
  • The average-case running time, which refers to the average running time where the average is taken over all possible inputs of size n.

GROWTH RATE

The growth rate of a function has to do with the rate at which the value of the function changes as the size of its input increases. The growth rate gives the general shape of the function, rather than its specific value.

Looking at growth rates in this way is sometimes called asymptotic analysis, where the term asymptotic” carries the connotation of for large values of n.”

NOTATIONS

O‍‍‍‍-Notation

It bounds the function to within constant factors.

We say  f(n) = O(g(n))  if there exists positive constant n0,c1 and c2 such that to the right of n0 the value of f(n) always lies between c1g(n) and c2g(n).

O-Notation

This gives the upper bound. It gives f(n) = O(g(n))  if there are positive constants n0 and c such that to the right of n0, the value of f(n) always lies on or below cg(n).

Ω- Notation

It says f(n) =   Ω g(n)   if there are positive constants n0 and c such that to the right of n0, the value of f(n) always lies on or above cg(n).