Data Structures

Assumptions:

We will assume that you have studied Programming Fundamentals and Object Oriented Programming from our blog.

Introduction:

Why Data Structures? Data structures helps you in becoming a good programmer. Data Structures do not involve any new syntax. The basis of data structures is only the concepts. Data Structures help you to sort, find, delete, add and update data in efficient way. So far, we have used linear search methods to search for any entry in array. This will take much time if we have huge data. Therefore, to find any data very quickly, we use Data Structures.

We will discuss time complexity here. Click any of the following to view details about that data structure:

1. Linked List
2. Singly, Doubly and Circular Linked List
   
3. Stack and Queues
4. Recursion
5. Tree
6. Binary Search Tree (BST)
7. Balanced Binary Search Tree (AVL)
8. Heap Search
9. Heap Sort
10. Hashing
11. Graphs

Time Complexity:

The time taken by any program to execute is called time complexity of that program. In real life the programs executes very fast. Therefore, for our convenience we assume that every line of code take 1 unit time.

Let say:

cout<<"Hello World!"<<endl

This line will take 1 unit time according to our assumption. Ignoring include files and main.

Now let say we have a loop. What will be the time complexity of the program in that case?

Let say we have

for (int i=0; i<10; i++)

{

     cout<<i<<"  ";

}

This program will print counting from 0 to 9. int i=0; in for loop will be done only one time as in for loop the variables are initialize only in start of for loop. The condition i<10 will be checked 11 times. Why? Because on termination when i will be running for 11th alteration after completing from 0 to 9 , it will check for i<10. This check will be its 11th alteration. i++ will be executed 10 times, because in first alteration it will not execute, this statement will run 10 times from i=0 to i=10. In the last the statement  cout<<i<<"  ";  statement will be 10. Why? Because this statement is controlled by for loop which runs 10 times therefore,  cout<<i<<"  "; statement 10 times.

We can say that the above lines of code have time complexity equals to 1 + 11 + 10 + 10 = 32.

Big O:

The Big O concept help us to reduce such an in depth analysis of program's time complexity. Big O gives us a close approximation about the time complexity of any program. It ignores the one line statements and only take into account of loops and the conditions that are controlling that loop. According to Big O this program has time complexity equal to O(N). Here N=10.

for (int i=0; i<10; i++)

{

     cout<<i<<"  ";

}