Analysis of Algorithms

Analysis means we analyze some prospects of algorithms using mathematical notations(generally) and deriving some conclusions out of it, even before writing code for the same. Before getting hands on analysis, we should know the following facts.
Characteristics of Algorithms:
Some of the basic characteristics of any algorithm are:
Input - zero or more inputs should be taken
Output - atleast one or more output should be given
Definiteness - every statement must be understandable by both human and computer
Finiteness - it must have finite no. of statements
Effectiveness - no necessary statements

The way of writing algorithm doesn't matter unless it is not understandable, we can write it in any manner.


We analyze time, i.e time efficiency or time complexity. We also mainly analyze space complexity. These two are the main and most important points of all for any algorithm. These are of so much preference because they play major role in runtime execution analysis.
But depending on what algorithm we are writing and for what we are writing, there can arise a need to consider other factors like network connectivity, data transfered, power consumption etc.
Consider algorithm for swaping values of two variables:
    Algorithm Swap (a, b):            
    temp ← a;  _______ 1 unit of time            
    a ← b;     _______ 1 unit of time            
    b ← temp;  _______ 1 unit of time           
    f(n) = 1 + 1 + 1 = 3 units of time → O(1)      
For a statement like x = 5*a + 6*b we can say its time units are 4, 2 for multiplication operations, 1 for addition and 1 for assignment. Or we can consider any operations to be significant, so we can take atmost 4 or atleast 1 unit for this statement. It's totally upon us.
For space: no of variables
    a → 1 word        
    c → 1 word        
    b → 1 word        
Total 3 words hence S(n) = 1 + 1 + 1 = 3 words → O(1)
We have used a notation of 'O()' for both f(n) & S(n). For now we have to accept a fact that if we get a constant value of function then it is of class O(1). We will discuss more on this Big O notation in another blog in this section of Algortihms itself.

Frequency count method for analysis:
Let's take another algo for sum of elements in an Array (A), where each statement takes 1 unit of time.
    Algortihm Sum(A,b):            
    s = 0;             __________ (1)
    for(i=0 ; i < n ; i++) ____(n+1)                
    s = s + A[i];    _____(n)            
    return s;         ____(1)          
    f(n) = 1+(n+1)+n+1 = 2n + 3     
The degree of polynomial f(n)= 2n+3 is 1. Hence Big O notation for time function is
O(n1) = O(n)
Space occupied:
    A → n words          
    n → 1 word          
    s → 1 word          
    i → 1 word       
    S(n) = n + 3 words      
The degree of polynomial S(n)= n+3 is 1. Hence Big O notation for space function is
O(n1) = O(n)
By performing this analysis we can control the space and time functions functions by making appropriate changes in operations or statements. You can find more on Big O notation O() in detail, along with Big Omega Ω(), and Theta Θ() notations in a dedicated blog for the topics.