Algorithms and Data Structures - P - 1.0

In this blog, you'll get to know

1. What are algorithms and data structures
2. Why algorithms
3. Example algorithms
4. How we benefit by learning these algorithms

What are algorithms and data structures

An algorithm could be defined as a computational step or a sequence of computational steps that transforms the input into the desired output. A data structure is a way of storing and organising data.

Why algorithms and data structures

Imagine a farmer and his mango-growing skills

Algorithm ====> Skill to grow mango trees
Input Data ====> Mango seeds
Output Data ====> Ripe Tasty Mangoes

A farmer uses his mango growing skills(algorithm) to transform mango seeds(input data) into ripe mangoes(desired output), similarly, all the available algorithms help us to process the data and transform/derive the output from it.

Example algorithms

1. Insertion sort : Used to sort an array
2. Breadth-first search : Used to search an element
3. Lempel–Ziv–Welch (LZW): Used to compress data

These are some sample algorithms, from compressing files inside a pen drive to transferring data over the internet everything is governed by algorithms and knowledge of these algorithms helps us design efficient systems.

How we benefit by learning these algorithms

Let's take up an example and understand how a beautiful sorting algorithm speeds up the process of sorting a set of inputs mathematically.

Insertion Sort

For n number of elements in an array, the time taken by insertion sort is
c1*n^2 ------------------- (1)
c1 ---> Independent constant that does not depend on n
n ---> Number of elements

Merge Sort

For n number of elements in an array, the time taken by merge sort is
c2*n*ln(n) ------------------- (2)
ln(n) ---> log(n) to the base 2
c2 ---> Independent constant that does not depend on n
n ---> Number of elements

Let's Compare their performance

There are two computers A(imagine A is faster than B) and B(imagine B is slower than A)
A --> Processes 10^10 instructions/second
B --> Processes 10^7 instructions/second
c1--> 2
c2--> 50
n --> 10^7

By applying the above data :
Computer A takes
(2*(10^7)^2)/(10^10) = 5.5 hrs(approx)

Computer B takes
(50*(10^7)*ln(10^7))/(10^7) = less than 20 mins(approx)

Even though computer B is slower than computer A, with an efficient algorithm like merge sort and for large data like 10 million records computer B is able to sort faster compared to computer A(NOTE: this holds good for large values of n like 10 million)

We could infer from the above observation that by having good knowledge of algorithms we would be able to efficiently use our resources like CPU, Memory(RAM).