Data_structures

what is data structures ? 

It is a way to organize the data 


There are various kinds of data structures 

Arrays,linked_list,Trees etc 

what are arrays:
a collection of elements with similar data type is called the arrays 

what are linked_list ? 

it is a node holding the data and it also contains the address of the next node 

what are trees ? 

it has leaves,branches,roots 


so if we see all these data structures are holding the data in there own way 


what is an algorithm ? 

an algorithm is the step by step process we perform to organize the data 


It is a way to solve particular problem 


so what is time complexity ? 

lets see this with an example for better understanding lets take an array [1,2,3,4,5,6] so if we want to know waht is the 5th index we can take it directly the operations we are taking to do that is "1" 


now if we see the linked list 

[5] -> [6] -> [4] -> [9] 

so here if we wants to access one element we can take it directly because every node holds the address of the next node so we have to follow the sequential order 


now lets understand the time complexity : in an array of [1,9,7,5,4,2,6] if we wants to know whether the element 4 is there are not what we do we first check from beginning 1 no, 9 no,7 no,5 no,4 yes here 


so like this we check here so what is the best case we can find the 4 in this array it is 1 means when we start searching for element 4 we have to find it in the 1st place what is the worst case finding  the element 4 in the last place 
so here :
    best case : 1 
    worst case : lenght of the array and last element in that 


so every time we take worst case 

so we denote the worst case with O-> Big O 

the no of elements in the array is n 


so O(n) 



now we underatand what is O lets move forward 
 
now lets take an array = [1,3,5,8,10,12,15,30,57,63,90] 
                          0 1 2 3  4  5  6  7 8  9  10 

we see this is the sorted array what is sorted means the array is in ascending order like low to high 


now if this array is not sorted and if we wants to find one number or element from this we have to search one by one like we done before check 1 check 3 like that but if we see this is the sorted array so
we can do it easily like :

as the array is sorted we can use binary search.

here we see binary search it is an algorithm 

lets see it 

so the algorithm is :
lets think we want to find the number 57 in in the array to find 57 we use binary search 
lets see :

first check the length of the array 

it is 11 so now do : 0 + 10 /2 what is the output  you can say i have 11 elements but starting from 0 it is 10 
so 0 + 10/2 is 5 

lets go to 5th element now check whether the element at 5 index is greater then the desired number(57) or not so move the elements of that array to aside 

now the elements we are having in the array are [15,30,57,63,90]
                                                 0  1  2  3   4 



now again (0 + 4) /2  which is 2 check the element at index 3 which is 57 now compare the desired element is less then or greater then or equal to the element 

so as our number is equal to the 57 our output and our index is 8 that's it 


so here we see every time the operations are decreasing to half if there are 100 element first iteration 50

second 25 
third 11 

like that it is becoming half so 
the time complexity is O( log n) 


here we have seen the sorted array to sort that array we need sorting techniques: quick sort and merge sort 


so till now we learned:
 O(1)
O(log n ) 
O(n) 


let's move forward and learn more 

for suppose there is an array : [1,5,3,8,9,10,4,3,15,18,20] 

now the question is to find the duplicates in the array means find the similar elements in the array :
lets see our approach 

now if we see the approach we used the 2 loops to search for the duplicate elements 

the approach is 1 doing search on : 5,3,8,9,10,4,3,15,18,20 

a = [1,5,3,8,9,10,4,3,15,18,20]

for i in range(len(a)):
    for j in range(i + 1,len(a)):
        if (a[i] == a[j]):
            print(a[j])


the Time Complexity for this = O(n ^ 2)
space complexity is O(1) 

Time complexity is O(n^2) for sorting the array 
for using for loop the the time complexity is O(n) so O(n^2 ) + O(n) ~ O(n^2) which 


now if we sort this array and do the process :

a = [1,5,3,8,9,10,4,3,15,18,20]
a.sort()

for i in range(1,len(a)):
    if a[i] == a[i - 1]:
        print(a[i - 1])
   
Time complexity is O(n log n) for sorting the array 
for using for loop the the time complexity is O(n) so O(n log n ) + O(n) ~ O(n log n) which 


for 2 loops O(n ^2) for 3 loops O(n ^3) 


now the time complexities we learn upto :

O(1) 
O(log n) 
O(n) 
O(n log n )
O(n^ 2) 
O(n^3)
these 2 are different cases we dont go upto here:  
O(2^n)
O(n!) 




the problems are started and if the problem needs any algorithm we will discuss it ther