Analysis of algorithm

by · Published · Updated

Every algorithm must be verified while designing it and its accuracy must be estimated, this is obtained by evaluating the algorithm. The algorithm can be evaluated by tracing all step by step instructions, analyzing for logical correctness and testing over some correctly chosen test cases or using mathematical techniques to prove it correct. Algorithms can also be analyzed in another way by analyzing the simplicity of the algorithm. I.e. design the algorithm in a simpler way to make it easier to b implement. However, the simplest and straightforward solution for a problem may not always be the best and optimized answer. There may exist multiple algorithms for a single problem. The choice of an algorithm depends on following performance analysis and measurements :

  1. Space complexity
  2. Time complexity

SPACE COMPLEXITY

The space complexity of an algorithm or program is the analysis of the amount of memory it needs to run to completion.
Some of the reasons for studying space complexity are:

  • If the program is to run on a multi-user system, it may be required to specify the amount of memory to be allocated to the program.
  • We may be interested to know in advance whether sufficient memory is available to run the program.
  • There may be multiple possible solutions i.e. algorithm with different space requirements for a single problem.
  • The size of the largest problem that the program can solve that can be estimated.

The space needed by a program consists of the following components.

  1. Instruction space: It refers to the fixed Space that is required to store the executable version of the program or instructions/opcodes.
  2. Data space: Space required to store all variable, constants values and has further three components :
    • (a) Space required by simple variables and constants. This space is fixed for most of the cases.
    • (b) Space required by fixed-sized structural variables, such as structures and arrays.
    • (c) Dynamically allocated space. This space usually varies as they may be allocated in runtime.
  3. Environment stack space: This space is required to store the information to resume the suspended/partially completed functions/methods. Each time a function is invoked the following data is saved on the environment stack :
    • (a) Return address: that is, from which address it has to resume after completion of the called function.
    • (b) Values of all lead variables and the values of all formal parameters in the function being invoked.

The amount of space required by the recursive function is known as the recursion stack space. For each recursive function, this stack space depends on the space needed by the formal parameters and the local variables. This space depends on the maximum recursion depth i.e., the maximum number of nested recursive calls it can perform.

TIME COMPLEXITY

TIME COMPLEXITY

The time complexity of an algorithm or a program is the amount of time it requires to execute to its completion. The exact time required will depend on the implementation of the algorithm, programming language, the CPU clock speed, optimizing the capabilities of the compiler used, other hardware characteristics/specifications and so on. To measure the time complexity accurately, all sorts of operations performed in an algorithm to be counted. If the time for each of the primitive operations performed in a given system is known, the time taken by an algorithm to complete its execution can easily be computed. This execution time will vary from machine to machine. By analyzing an algorithm, coming out with an exact time required is not so easy. To find out the exact time complexity, we need to know the exact instructions executed by the hardware and the time required for the instruction and many more. The amount of data inputted to an algorithm also contributes to its time complexity. But the order of magnitude for the time required can be calculated.

Our intention is to estimate the execution time of an algorithm irrespective of the computer machine on which it will be executed. Here, identifying the key operations and count such operations performed until the program execution completes is the more sophisticated method. Here, a key operation is an operation that takes maximum time among all possible operations in the algorithm. Such an abstract, theoretical approach is useful for both discussing & comparing algorithms and to improve solutions to practical problems. The time complexity can now be expressed as a function of the number of key operations performed. Before we go ahead with our discussions,
it is important to understand the rate growth analysis of an algorithm, as shown in Figure.

The function where ‘n’ is used as an exponent, i.e., 2^n , n^n, n ! are called exponential functions, which is too slow except for small size input function where growth is less than or equal to n^c ,(where ‘c’ is a constant) i.e. n^3, n^2, n log_2n, n, log_2n are said to be polynomial.
Algorithms with polynomial-time can solve reasonable sized problems for small constants.
When we analyze an algorithm, depends on the input data, there are three cases :

  • Best case
  • Average case
  • Worst case

In the best case, the amount of time a program might be expected to take on the best possible input data (least execution time).
In the average case, the amount of time a program might be expected to take on typical (or average) input data (lesser execution time).
In the worst case, the amount of time a program would take on the worst possible input configuration (largest execution time).

AMSTRONG COMPLEXITY

In many situations, data structures are subjected to a sequence of instructions rather than one set of instructions. In this sequence, one instruction may perform particular modifications that have an impact on other instructions in the sequence at the runtime itself. For example in a ‘for’ loop, there are 1k instructions in an ‘if’ statement. If the condition is ‘false’ then these 1k instructions will not be executed. If the time complexity analysis is applied in the worst case, the entire sequence is considered to compute its efficiency, which is an excessively huge and unrealistic analysis of efficiency. But when amortized complexity is applied, the complexity is calculated only when the instructions are executed (i.e., when the ‘if’ condition is true)

Here the time needed to execute a sequence of operations preferably related is averaged over all the operations performed. Amortized time complexity analysis can be applied to show that the average cost of operation is small, if one averages over a sequence of operations, even though an expensive simple operation. Amortized analysis guarantees the average performance of every operation in the worst case.

TIME-SPACE TRADE-OFF

There may be multiple approaches (or algorithm) to solve a problem. The best algorithm (or program) to solve a problem is one that requires less memory space and less execution time. In practice, it is not always possible to achieve both objectives. One algorithm may require less memory space but more time to complete its execution while the other algorithm requires more memory space but takes less time to complete its execution. Thus, we may have to consider one at the cost of the other. If space is the constraint, then a program that requires less space at the cost of more execution time to be chosen. On the other hand, if time is the constraint such as in real-time systems, a program that takes less time to complete its execution at the cost of more space to be chosen.

BIG “OH” NOTATION

Big Oh is a characteristic parameter that measures properties of algorithm complexity performance and/or memory requirements. The algorithm complexity can be determined by replacing the constant factors in the analysis of the algorithm. Clearly, the complexity function f(n^2) of an algorithm increases as 'n^2' increases.

Let’s find out the algorithm complexity by evaluating the sequential searching algorithm. In the sequential search algorithm, we simply try to match the target data to each data in the memory. This process will execute until we find a match or finish searching the whole array. If the array contains ‘n’ elements, the maximum number of comparisons possible with the target data will be ‘n’ i.e., the worst case. That is the target data will be found at the nth position of the array.
f (n) = n
i.e., the worst-case arises when an algorithm needs a maximum number of iterations or steps to search and find out the target data in the array.

The best case is when the number of iterations or steps is as less as possible. If the target data is found in a sequential search array at starting position (i.e., we need to compare the target data with only one element from the array)—we have found the element by only one iteration (or by least possible statements)
f (n) = 1

The average case falls between these two extremes (i.e., best case and worst case). If the target data is found at the n/2 ^n^d position, on an average, the target data is compared with only half of the elements in the array, so
f (n) = n/2
The complexity function f(n) of an algorithm grows as ‘n’ grows. The function f (n)= O(n) can be spelled as “f (n) is of the order of n” or as “f of n is big Oh of n”. The total execution time (or time complexity) contains the initializations and several other iterative statements through the loop.
The generalized form of the theorem is

f (n) = c_k n^k + c_k_-_1 n^k^-^1 + c_k_-_2 n^k^-^2 +...+ c_2 n^2 + c_1 n^1 + c_0 n^0 Where the constant c_k > 0

Then, f (n) = O(n^k)

Based on the time complexity representation of the big Oh notation, the algorithms can be classified as :

  • Constant time O(1)
  • Logarithmic time Olog(n)
  • Linear time O(n)
  • Polynomial time O(n^c) Where c > 1
  • Exponential time O(cn) Where c > 1

LIMITATION OF BIG “OH” NOTATION

Big Oh Notation has following two basic limitations :

  1. It holds no effort to improve the programming methodology. Big Oh Notation does not tell the means and methods to improve the efficiency of the program, but it helps to calculate and analyze the efficiency (by determining the time complexity) of the program.
  2. It does not discuss the potential of the constants. For example, one algorithm is taking 1000n^2 time to execute and the other n^3 time. The first algorithm is O(n^2), which means that it will take less time than the other algorithm which is O(n^3). However, in actual execution, the second algorithm will be faster for n < 1000.

One suitable algorithm to be chosen to optimize requirements.

Tags:

You may also like...

Leave a Reply

Your email address will not be published.