What is an algorithm and how to calculate complexity of algorithms.?

Web Development
,
#1

Algorithm complexity is a measure which evaluates the order of the count of operations, performed by a given or algorithm as a function of the size of the input data. To put this simpler, complexity is a rough approximation of the number of steps necessary to execute an algorithm.

What is an algorithm?
An algorithm is step by step instructions to solve given problem.
Lets take a simple example.You want to write an algorithm for listening particular song.

  1. Search for song on computer.
  2. Is song available?
    i.If Yes,Then listen that song.
    ii.If no,download that song and then listen that song.
    So we are solving a problem by step by step procedure.This step by step instructions is called Algorithm.

Why do you need to evaluate an algorithm?

You need to evaluate an algorithm so that you can find most optimize algorithm for solving given problem and also considering various factors and constraints.

For example:

You want to go from city A to City B.Then there are various choices available i.e. by flight,bus or train.So you need to choose among different options depending on your budget and urgency.

Counting number of instructions:

Number of instructions can be different for different programming languages.

Lets count number of instruction for searching a element in a array.

int n=array.length
for (int i = 0; i < n; i++) {

if(array[i]==elementToBeSearched)
return true;
}
return false;

Let’s assume our processor takes one instruction for each of the operation:

  • For assigning a value to a variable
  • For comparting two values
  • Multiply or addition
  • Return statement

In Worst case:

If element which we want to search is last element in sorted array then it will be worst case here.
So :

1

2

3

4

5 if(array[i]==elementToBeSearched) ,i++ and i<n will be executed n times

int n=array.length,i=0,return true or false will be executed one time.

Hence f(n)=3n+3

Asymptotic behaviour :

Here We will see how f(n) performs with larger value of n.Now in above function, we have two parts i.e. 3n and 3. Here you can note two points:

  • As n grows larger, we can ignore constant 3 as it will be always 3 irrespective of value of n. It makes sense as you can consider 3 as initialization constant and different language may take different time for initialization.So other function remains f(n)=3n.
  • We can ignore constant multiplier as different programming language may compile the code differently. For example array look up may take different number of instructions in different languages. So what we are left with is f(n)=n
#2

There are two types of Complexities:

  1. Time Complexity: Amount of time taken by an algorithm to run as a function of the length of the string representing the input. The time complexity of an algorithm is commonly expressed using big O notation. There are again 3 categories

  2. Best Case: algorithm’s behavior under optimal conditions.

  3. Average Case: amount of some computational time used by the algorithm, averaged over all possible inputs

  4. Worst Case: longest running time performed by an algorithm given any input of size n

  5. Space Complexity: Space required for and algorithm

Time complexity is a major concern out of which Worst Case complexity is important.