sridharavulapati

Algorithm: It can be defined as method of solving a given problem.
Data Structure: Its is a method to store information.

Algorithms + Data Structures = Programs.

A Good programmer is the one who worries about the data structures rather than code – Linus Torvalds (creator of Linux)

Why do we analyse alogithms?

Some of the reasons include to predict the performance, Compare with other algorithms.
If we observe in any IT Organisation, Client feel dissatisfied few times. Reason behind that is programmer did not understand performance characterisitcs. Ohh.. too much to think at this point of time..

Writing an algorithm is not sufficient. If we analyse how good the algorithm works at any given point of time is very important. For that we need to figure out how it works in best case, worst case, normal case. These three cases are well-defined by the checking the complexity of the Algorithm.

There are two types of complexity of Algorithm which used to describe the cases how your Algorithm is working as follows.

Time Complexity >>Amount of time taken by an algorithm to run for compilation i.e execution
Space Complexity>> Amount of memory an Algorithm needs to run to Compilation

What is Big-O notation?
It measures how well an operation will “scale” when you increase the amount of “things” it operates on.
Big-O can be used to describe how fast an algorithm will run, or it can describe other behaviour such as how much memory an algorithm will use. For the purposes of this article, we’re only going to focus on Big-O as it relates to runtime.
Big O specifically describes the worst-case scenario

O(1)

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set. No matter how large the input is, the time taken doesn’t change. Say for example “Check whether a number is even or Odd.”

Sample Code:
boolean is_first_element_null(array)
    if(array[0] == null) {
        return true;
    }
    return false;
}

O(n)

This means, we are doing constant number of operations for each element that we have in hand. Like, Comparing two strings.

Sample Code:
boolean checkName(String[] names, String nameToCheck) {
      for(int i = 0; i < names.Length; i++) {
          if(names[i] == nameToCheck){
                return true;
          }
      } return false;
}

Here we compare eave name in Names array to a given name. So this grows linearly to the size of array. Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

O(n2)

This means that for every element, you do something with every other element, such as comparing them. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.

Sample Code:
boolean ContainsDuplicates(String[] strings) 
{
       for(int i = 0; i < strings.Length; i++) {
             for(int j = 0; j < strings.Length; j++) {
                   if(i == j) // Don't compare with self
                       { continue; }
                   if(strings[i] == strings[j])
                       { return true; }
             }
        }
        return false;
}

O(2 ⁿ)

It means, Time taken will be double the time, for each addition element in the input data. Otherway … whose growth will double with each additional element in the input data set.

O(n log n)

It means, we are performing an O(log n) operation for each item in your input . Every time you double n, you spend twice as much time plus a little more. The operation will take longer as the input size increases, but once the input gets fairly large it won’t change enough to worry about. If you double n, you have to spend an extra amount of time t to complete the task. If n doubles again, t won’t double, but will increase by a constant amount.

Consider binary search example. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.

This type of algorithm is described as O(log N)

This example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase.

O(n!)

O(n!) involves doing something for all possible permutations of the n elements.

We can obtain some general formula or methods for all arithmetic operation which perform at runtime is given by as follows:
T(n) = C1 Mul(n) + C2 Add(n) + C3 Sub(n)+…………………………………….+Cn Mul(n)
Here T denotes for time complexity and C1, C2, C3,Cn denotes for the cost taken by the algorithm to execute .

public class Analyse {
    public static void main(String[] args) {
      int a, b, c, d, i;                  
          // This takes 1 unit of time. Assume cost for this is C1
          for (i = 0; i <= 9; i++) {       
             // This takes 11 units of time.Assume cost for this is C2
              c = a + b;                 
      // This line of code gets executed for 10 times. So it takes 10 units of time. Cost is C3
                 d = b + 1;    
      // This line of code gets executed for 10 times. So it takes 10 units of time. Cost is C4
           }
                 d = c + d;    
     // This takes 1 unit of time. Assume cost for this is C5
      }
}

Calculating Time Complexity of above example.
=> T(n) = C1*1 +C2*11 + C3*10 + C4*10 + C5*1
=> T(n) = 1*(C1+C5) + 10*(C3+C4) + C2 * 11
=> T(n) = O(11)                            <———-Ans.

//