Complexity of Algorithm - DSA
Powered by Blogger.

Monday, May 2, 2022

Complexity of Algorithm

Complexity means classifying an algorithm based on the amount of time and space an algorithm needs to specify the growth of time/space requirements as a function of the input size. so we have two things to measure the complexity of the algorithm.


Complexity of Algorithm

Time complexity

It measures the running time of the program as a function relative to the input size. running time is always equivalent to the steps or operations that are executed before termination.


Space complexity

It measures the amount of memory an algorithm required to execute as a function of the input size.


Let's say we have an algorithm A and need to enter the N size of input data. to measure the efficiency of the algorithm we need to measure the time and space used by the algorithm. to measure the time we need to calculate the number of key operations. for example in the searching algorithm we need to search for an algorithm and compare it with each item in the list. so the time complexity is defined as the time for the other operations we need and space is measured by counting the maximum memory we need to store those operations.


In simple terms, the storage space required by an algorithm is multiple of the data size N. and the complexity of an algorithm is the function f(n) that given both time and space complexity of the algorithm.


Measurement of Complexity

  1. The complexity of an algorithm depends on a number of factors like
  2. The time complexity of an algorithm.
  3. Input data of the program.
  4. Implementation of program.
  5. Code generation of the compiler.
  6. Machine used to run the program.


Without producing the theory of an algorithm we can describe the algorithm in the above-given points. there are some points that are only valid for the algorithms implemented in a particular programming language by a particular programmer using a particular compiler and executing on a particular machine. so we have to abstract all these points before applying the algorithm.


we can describe algorithms in pseudo-code to implement in a programming language that can only be understood by the programmers. so it is not in a formal way. let's say we have an algorithm in terms of pseudocode and each step of pseudocode can be executed in a constant time no matter which machine we are using or which compiler we are using. also, it does not depend on the variables' size.


Let's say we have an algorithm that searches for an integer in an array of integers described in pseudocode and implemented in the java programming. so we need to compare the pseudocode with the actual implementation in java.


Pseudocode

Algorithm research(A,k)

Input: An integer array A, an integer k

Output: the smallest index I with A[i] = k, if such I exist, or -1 otherwise.

1. for i <-- to A.length -1 do

2. if A[i] = k then

3. return i

4. return -1

public static int seqSearch(int [] A, int k)

{

    for(int i=0, i < A.legth; i++)

    if (A[i] == k)

    return 1;

    return -1;

}


Let's say we have the input consisting of the array A={1,2,3,4,5,6,9,7} and the integer k=0 and the length of A=8. so we want to get the estimate of seqSearch when these inputs apply and what is the number of estimate machine cycles to execute the algorithm. to compute or estimate the actual runtime we usually need to multiply the computation steps by the clock speed of our machine.


Unfortunately, we do not know what the execution of a line can complete in how many steps. because this depends on a number of factors like a programming language, compiler, and the instruction set of the CPU. but we can say that for implementation of an algorithm on a standard machine will require a small constant number of steps. means a constant number that does not depend on the value of I and length A. and let's say line 2,3,4 requires at most steps to complete. let's say we can represent these steps by A1, A2, and A3.


using the input A={1,2,3,4,5,6,9,7} we can compute the number of steps when k=0. so we can say that line 1 can execute 8 times and line 2 is also executed 8 times. line 3 is executed once, and line 4 is never executed. so the most computation steps are

8A1 + 8A2 + A3

so for every input, we can calculate this function. and we can define a function of the size of the input that is the length of A. also depending on the number where it is found or appears in the array. we resolve this by giving the estimation of the number of computation steps needed in any case like worst, average, and best case.