Algorithm Analysis

For every algorithm we write and implement data structure using different methodologies but to consider which methodology is best we need to compare and that comparison is nothing but analysis of algorithm.

Analysis of algorithm can be done in two ways -

1. Space complexity:

Additional space (Number of elements is stored) required to run a programme is called Space Complexity.

• It wouldn't include Space occupied by inputs.

• It is the space that is required while executing the programme. The output of the algorithm can be included in space complexity, if it takes more than desired space.

2. Runtime complexity:

Time required to run the algorithm is called Runtime Complexity. Item measuring two ways -

• On clock time: In this it measure the time in nanosecond or second for each execution.

  But it changes frequently for every time we run the programme because the wall clock time depends on various factors of operating system such as interrupt generated background processes, hardware connected peripheral devices interrupt etc.

• Number of operations: In this runtime complexity is measured in terms of number of operations required to complete the execution of the program.

  Here the runtime complexity will depend on the number of inputs so it will be written in some standard form in terms of n.

For every algorithm there are two types of cases in terms of time complexity-

Best Case: The type of input for which algorithm takes minimum time.

Worst Case: The type of input for which algorithm maximum time.

Rate of Growth

With what rate runtime complexity increases with increment in input size.

The runtime complexity for above will be - T(n) = n + 2

So, we can say that the runtime complexity is increasing linearly. Following up some complexity, depend on the rate of growth.

Asymptotic Notation

A mathematical representation to represent the time space complexity is called asymptotic notation.

Basically it is of three types -

Big O Notation (O)

• Define an upper bound of an algorithm.

• It gives non-negative f(n) and g(n) defines on a positive integer so we can say that f(n) = O(g(n)) Is there exists a positive integer n0 and positive constant C such that -

  f(n) ≤ C . O(g(n)) ∀ n >= n0 i.e., growth rate of g(n) should be greater than f(n).

• 

Omega Notation (Ω)

• Define an lower bound of an algorithm.

• It gives non-negative f(n) and g(n) defines on a positive integer so we can say that f(n) = Ω(g(n)) Is there exists a positive integer n0 and positive constant C such that -

  f(n) ≥ C . Ω(g(n)) ∀ n >= n0 i.e., growth rate of g(n) should be less than f(n).

Theta Notation (θ)

• Provide asymptotic equal bound.

• It gives non-negative f(n) and g(n) defines on a positive integer so we can say that f(n) = θ(g(n)) Is there exists a positive integer n0 and positive constant C1 and C2 such that -

  C1 . θ(g(n)) ≤ f(n) ≤ C2 . θ(g(n)) ∀ n >= n0 i.e., growth rate of f(n) should be equal to g(n).

Examples

Example 1 -

for (i = 0; i <= n; i++){
    x = m + 2;
}

So the runtime complexity for the above example will be -

Example 2 -

for (i = 0; i <= n; i++){
    for (j = 0; j <= n; j++){
        x = m + 2;
    }
}

So the runtime complexity for above programme will be

Example 3 -

for (i = 0; i <= n; i++){
    for (j = 0; j <= n; j++){
        for (k = 0; k <= n; k++){
            x = m + 2;
        }
    }
}

So the runtime complexity for above programme will be -

Example 4 -

for (i = 0; i <= n; i=i*2){
    x = m + 2;
}

So the runtime complexity for above programme will be -

Example 5 -

for (i = 0; i <= n; i=i*2){
    for (j = 0; j <= n; j=j*2){
        x = m + 2;
    }
}

So the runtime complexity for above programme will be

Example 6 -

for (i = 0; i <= m; i++){
        a = a + sqrt(i);
}
for (j = 0; j <= n; j++){
        b = b + sqrt(j);
}

So the runtime complexity for above programme will be

Example 7 -

for (i = 1; i <= n; i++){
    for (j = 1; j <= i; j++){
        x = m + 2;
    }
}

So the runtime complexity for above programme will be

for i = 2 loop will run 2 times,
for i = 3 loop will run 3 times,
.
.
.
for i = n loop will run n times,

So, it will be -
1 + 2 + 3 + . . . + n = (n (n + 1)) / 2 = (n<sup>2</sup> + n) / 2 | | Total Complexity | ((n² + n) / 2 ) + n → θ(n<sup>2</sup>) |

Conclusion

In algorithm analysis, understanding space and runtime complexities through Big O notation helps assess efficiency. Examples illustrate complexities like linear, quadratic, and logarithmic, aiding algorithm optimization.