DATA STRUCTURES AND ALGORITHMS

*

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 :

1. Time complexity
2. 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.

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.