Complexity of Algorithms

aka: performance analysis or efficiency of a program

To analyse an algorithm

  1. First determine the operations the are included like additions,subtractions,multiplication and divisoin to find their relative cost.
  2. Comparisions generally take longer
An algorithm can be analysed in two ways :
  • The correctness of an algorithm
  • By measureing time and space complexity of an algorithm
    • Two phases are generally required :
  • Priori analysis
  • Posteriori Analysis


    • Priori Analysis

    Give an initial state input data
    We need to determine the total time some statements in the middle of the program will spend for the execution
    Requirements:
    1. The statemtns frequency count [ The number of times a statement will execute ]
    2. The time taken for one execution
    The product of these two numbers is the total time

    It ignores the following factors
    1. The machine's cpu process capacity and speed
    2. The programming language and compiler that is been used
    The notation used in priori analysis are :
    1. Big-oh [O]
    2. Omega [Ω]
    3. Theta [Θ]
    4. Small-oh [o]

    Posteriori Analysis

    We will collect the actual statistics about the algortihm , conjunction of the time and space while executing
    Once the algorithm is written it has to be tested, which consists of two phases :
    1. Debugging: It is the process of correcting the algorithm if a fault result occurs . Independent of the machine, programming langauge, compiler used
    2. Profiling:The process of executing the program and measuring the actual time taken by the algorithm to process the data is called profiling [ could include measuring the space as well ] . Dependent of the machine, programming language and the compiler used
    In order to perform these we need to consider :
    1. Time complexity
    2. Space complexity

    Space complexity

    The amount of memory required by the algorithm to run to completion
    Ignoring the space required for input and output , since we use this information to compare different algorithm
    There are two compoenents for the space required by an algorithm
    The Fixed static part
    1. Independent of the characterisitcs of the input and output
    2. Instructions space for variables , constants, fixed size component variables
    The Variable dynamic part
    1. The space required by the a component variable who size depends on the particular problem instance at runtime being solved,
    2. The space needed by the reference variable
    3. The recurrence stack
    The overall space required for an algorithm is the sum of both the fixed and variable [ i.e static and dynamic ] part of the storage .



    Time Complexity

    The amount of time needed to run the program is termed as time efficiency or time complexity
  • The total time taken by the program is the sum of compile time and the runtime
  • The compile time does not depend on the instance characterisitcs and it can be assumed as a constant factor , so we ignore it

    • Bubble sort

    The most simplest form of sorting algorithm
    Works optimal only on small arrays
    With each iterations the value moves on top of the array just like a bubble


    Code

      
void bubble sort(int a[],int n){

int pass,i;

for (pass=0;pass < n-1;pass++){
for (i=0;i<n-pass-1;i++){

if (a[i]>a[i+1])
swap(a[i],a[i+1]);

}
}

}
    The time complexity for bubble sort is :
  • its compares every adjacent elements - all n elements , but since it compares 2 elements in the first go itself : n-1
  • Once the above step reaches the end of the array - one elements [largest,smallest] is sorted , so the next iterations with ignore that [first/ last] element making the second iteration : n-2
    • So the final time complexity is (n-1)+(n-2)+(n-3)+(n-4)=(n(n-1))/2
    that is (n² - n )/ 2 ,
    Since n² is larger than n and neglecting the constant "2"
    Bubble Sort's Time Complexity : n²
  • No merge sort is not for begineer - every person who takes birth can sort using merge sort - its not even an algorithm at this points
  • A step count is the steps per execution i.e the number of times that particular line has been executed in one instance of "program execution" , summation of all the number of executions of these lines in the program would be the step count of that program . The count that we use to determine the time complexity is the operation count
    • Order of Growth