DATA STRUCTURES AND ALGORITHMS

kenkomu — Tue, 21 Jun 2022 07:16:17 +0000

WHAT IS DATA STRUCTURES

Data Structures are the programmatic way of storing data so that data can be used efficiently.

WHAT IS ALGORITHMS

A finite sequence of instructions, each
of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time.

Applications of Data Structure and Algorithms

From the data structure point of view, following are some important categories of algorithms −

Search − Algorithm to search an item in a data structure.
Sort − Algorithm to sort items in a certain order.
Insert − Algorithm to insert item in a data structure.
Update − Algorithm to update an existing item in a data
structure.
Delete − Algorithm to delete an existing item from a data
structure.

Characteristics of an Algorithm

Unambiguous − Algorithm should be clear and unambiguous.
Each of its steps (or phases), and their inputs/outputs
should be clear and must lead to only one meaning.
Input − An algorithm should have 0 or more well-defined
inputs.
Output − An algorithm should have 1 or more well-defined
outputs, and should match the desired output.
Finiteness − Algorithms must terminate after a finite
number of steps.
Feasibility − Should be feasible with the available
resources.
Independent − An algorithm should have step-by-step
directions, which should be independent of any programming
code.

An algorithm is said to be efficient and fast, if it takes less time to execute and consumes less memory space. The performance of an algorithm is measured on the basis of following properties :

Time complexity
Space complexity

When we are analysing the complexity of any algorithm in terms of time and space,we can never provide an exact number to define the time required and the space required by the algorithm, instead we express it using some standard notations, also known as Asymptotic Notations.

Space Complexity of Algorithms

Space complexity is the amount of memory used by the algorithm (including the input values to the algorithm) to execute and produce the result.

Calculating the Space Complexity

While calculating space complexity, we need to know the value of memory used by different types of datatypes variable.

Type	Size
bool, char, unsigned char, signed char, __int8	1 byte
__int16, short, unsigned short, wchar_t, __wchar_t	2 bytes
float, __int32, int, unsigned int, long, unsigned long	4 bytes
double, __int64, long double, long long	8 bytes

Example 1:

{
    int x = a + b ;
    return(x);
}

In the above example, variables x, a, and b are all integer types, which will take up 4 bytes each, so the total memory requirement will be (3(4) +4 = 20 bytes, this additional 4 bytes is for return value. And because this space requirement is fixed for the above example, hence it is called Constant Space Complexity.

Example 2:

// n is the length of array a[]
int division(int a[], int n)
{
    int x = 0;      // 4 bytes for x
    for(int i = 0; i < n; i++)  // 4 bytes for i
    {   
        x  = x / a[i];      
    }
    return(x);
}

In the above code, 4*n bytes of space is required for the array a[] elements.
4 bytes each for x, n, i and the return value.
Hence the total memory requirement will be (4n + 12), which is increasing linearly with the increase in the input value n, hence it is called as Linear Space Complexity.

Time Complexity of Algorithms

For any defined problem which must be solved using a program, there can be infinite number of solutions.

Time complexity of an algorithm signifies the total time required by the program to run till its completion.

The time complexity of algorithms is most commonly expressed using the big O notation. It's an asymptotic notation to represent the time complexity.
since the algorithm's performance may vary with different types of input data, hence for an algorithm we usually use the worst-case Time complexity of an algorithm because that is the maximum time taken for any input size.

DEV Community: kenkomu