Wanna Deep Dive in Data Structures?

What is Data Structures:

Word Data Structures is comprised of two words

data and structures

Data: Collection of facts and figures.

Structure:- Structure means definite shape.

So, the word data structure means to transform the data in a particular form to or apply intelligent techniques on data to process data efficiently and effectively.

Before Getting into Data Structures. Let's have a look at some other topics to be able to understand this term a lot better.

What is an Algorithm:

A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

In simple words, It is just a set of steps to solve a particular problem.

For Example:-

Algorithm of making tea.

Put the teabag in a cup.

1. Fill the kettle with water.
2. Boil the water in the kettle.
3. Pour some of the boiled water into the cup.
4. Add milk to the cup.
5. Add sugar to the cup.
6. Stir the tea.
7. Drink the tea.

What is meant by the complexity of the Algorithm:-

The complexity of an algorithm is a measure of the amount of time and/or space required by an algorithm for an input of a given size (n).

In simple words, it is just the amount of or space or time that a program takes to perform a particular problem.

Types of Complexity:

1. Space Complexity
2. Time Complexity

Space Complexity:-

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of the characteristics of the input. It is the memory required by an algorithm until it executes completely.

In simple words, it is just the space that a program acquires to complete its execution.

Time Complexity:-

Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input. It measures the time taken to execute each statement of code in an algorithm.

In simple words, it is just the time taken by a program to complete its execution.

The complexity is written as O(<some function>), which is called the big O notation.

What is Big O Notation:-

A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n).

In simple words, it is just a notation/way to express the complexity of an algorithm.

How to calculate a Complexity of An Algorithms:-

I will take few pieces of code and will find their complexity

1-Linear Complexity:-

for( let i= 0; i<=n; n++){

print(n)

}

now think of the print statement. How many times this will be executed. N times so, Its Time Complexity is O(n).

2-Quadratic Complexity:-

for( let i= 0; i<=n; n++){ //loop1

for (let j=0; j<=n;n++){ //loop2

print(n)

}

}

now think of the above piece of code. Loop2 will execute n times for every iteration of loop1 which will be n*n. How many times print statement will be executed N *N times so, Its Time Complexity is O(n2).

3-Logarithmic Complexity:-

for( let i= 1; i<=n; i=i*2){

print(n)

}

This is not pretty straightforward. Let's analyze/execute it line by line

let's say we start when i=1

lets assume at this point I become greater than or equal to n. So,

I>=n

i.e. i=2k

So,

2k > n

k= log2 n

Hence the complexity of the algorithm is O(log2 n).

4:- Root Complexity:-

Now have a look at this code.

let p=0

for( let i= 1; p<=n; n++){

p=p+i;

}

this isn't pretty straight forward too. Let's execute it line by line

let say

Assume that the loop ends which is when p becomes greater than n I.e. P>n.

: P=k(k+1) / 2

so

=> k2+k>n

=> k2>n

=>k>√n

So the complexity of this algorithm is O(√n)

5:- Other Examples:-

for (i=0; i<n;i++) //this will execute for n times

{

for(j=1; j<n; j=j*2;){ //this will execute for log n times (for explanation see //logarithmic complexity)

statement; }

}

So the complexity of this algorithm is O(n log n).

6-Constant Complexity:-

let’s have a look at this piece of code

for(let i=0;i<=5; i++){

print (I) //this line will execute for 5 (definite) time this is constant complexity

}

Now we can say that

for( let i= 0; i<=n; i++)

for( let i= n; i>=1; i++)

Any loop that is either increment or decrement is Order of n O(n)

for( let i= 1; i<=n; i=i*2)

for( let i= 1; i<=n; i=i*3)

for( let i= 1; i<=n; i=i/2)

for( let i= 1; i<=n; i=i/2)

for a loop in which a number is being either divided or multiplied by any number then the complexity of that loop is the log of the number with which you multiply or divide the index.

I hope that you guys now have a basic understanding of the algorithm and complexity of an algorithm.

Let's Get back to the question.

What is Data Structures:

A data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Moving on

Types of Data Structures:-

• Linear: arrays, Linked-list, Queues, etc.
• Tree: binary, heaps, space partitioning, etc.
• Hash: distributed hash table, hash tree, etc.
• Graphs: decision, directed, etc.

Which Algorithm should we choose to solve a particular problem:

It really depends on one’s need and what he needs to do with the particular algorithm.

For example, if you need to search the number 2 out of a list of the first 100 numbers then

If you choose linear data structure sort to say a simple for loop then it will take exactly 2 iterations if we start to search from number 1 to reach the number 10.

But

If we perform a binary search to find the number 10 (which is just a searching algorithm) then it will take more than 2 iterations

Conclusion

If you found this post informative, please feel free to send me a connection request. If you found something missing, or wrong, please let me know in the comments so that everybody stays on the same page.