Algorithm:
- A set of procedural steps to solve a problem is called as algorithm
- analysis of algorithm mainly deals with : time, space, scalability
> time complexity : describes amount of time req to run algorithm
> space complexity : describes amount of space consumed based on size of
algorithm.
- types of analysis: with time
> worst case : we calculate the upper bound on running time of algorithm
: mostly used
: asymptotic notation : Big Oh(O)
> Average case : we calculate the average bound on running time of algorithm
: rarely used
: asymptotic notation : Big Theta
> best case : we calculate the lower bound on running time of algorithm
: never used
: asymptotic notation : Big Omega
- asymptotic behavior deals with large inputs( not all inputs)
Time Complexity:
O(1) :it indicates time complexity of method/program .
> it don't have loop, calling a method within this(recursion).
> Ex :
int a =10;
int b = 12;
int c = a+b;
O(n) :
> it have loop. run time of loop depends on n
>ex : n =10;
for(int j=0;j<n; j= j++){
........
}
O(n^c):
> it have nested loops. no of nested is (n^c)
> ex : for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
........
}
}
O(logn) :
> in a loop, if iteration includes in multiplication or division
>ex :
for(int j=0;j<10;j= j*2){
........
}
O(nlogn):
> nested loop & one of loop have multiplication or division in each iteration
> ex : for(int i=0;i<10;i++){
for(int j=0;j<10;j= j*2){
........
}
}
O(loglogn) :
> in a loop, if iteration includes exponential.
> ex : Math.pow()
Searching Algorithms:
--> to search an element based on complexity there are two ways :
--> Linear Search
--> Binary Search
--> Linear Search :
> searching an element by iterating and comparing that element.
> The number of iterations will be equal to the position of the number
being searched in case of linear search
> complexity
- best case : if element found at first of list
- worst case : if element found at last of list
--> Binary Search :
> Searching an element by subdividing array into two sub Arras
> The number of iterations will not equal to the position of the number
being searched in case of binary search
> disadvantages:
- list must be in sorted order
- it requires recursive , it consumes more stack memory space
> advantage :
- it works better than linear search when searching in larger data.
- time complexity is better than linear searching when dealing with
larger data
Sorting:
--> sorting of elements ascending order
--> two types:
- bubble sort
- merge sort
Bubble Sort:
-> max element in array is arranged in its position for every iteration by using
compareTo method
-> time complexity of bubble sort is : O(n2)
-> each iteration to sort element is called as pass
-> no. of passes cant decide as position of element may vary for each iteration
-> Worst case occurs when the elements are sorted in reverse order because all the
elements should be compared and swapped
Merge Sort:
-> divides unsorted list repeatedly into sublist contains only one element in each
sublist.
-> it is called demerging
-> merges the sublist of divided elements repeatedly to produce ascending order of
sorted list.
-> it is called merging.
-> Collections.sort() method uses merge sort.
- this method sorts the unsorted list in the ascending order.
-> merge sort is effectively used for sorting linked lists.
-> Merge sort is suitable for sorting large data set
-> advantage :
- sorts large list quickly compared to bubble sort.
