Please enable JavaScript.
Coggle requires JavaScript to display documents.
Analysis of Algorithm - Coggle Diagram
Analysis of Algorithm
Heap sort
-
-
-
Calculating # of nodes:
2^h , h= the depth of the nodes
Complete Binary tree:
all the levels are completely filled except possibly the lowest one, which is filled from the left.
Heap:
heap is a balanced, left justified binary tree in which no node has a value greater than the value in its parent (called max heap)
Left justified meaning:
if the tree nodes go from the left to right at the lowest level and the internal nodes are completely filled.
meaning by balanced:
that a binary tree of depth n is balanced when all the nodes at depth 0 through n-2 have two children.
heap is almost complete binary tree.
The main point is that if we want to insert any node at the lowest level of the tree, it should be inserted from the left. All the internal nodes should be completely filled
-
Best case: O(n log n) -linear & algorithmic-
Average case: O(n log n) -linear & algorithmic-
Worst case: O(n log n) -linear &algorithmic-
Algorithm
-
-
-
Growth Rates
O(1) ----> constant = 1 seconds
O(log n) ----> logarithmic = 4/3 seconds
O(n) ----> Linear = 2 seconds
O(n log n) ----> Linear & logarithmic= 8/3 seconds
O(n^2) ----> quadratic =4 seconds
O(n^3) -----> cubic = 8 seconds
O(2^n) -----> exponential = 2^8 seconds
-
Insertion sort
Best case: O(n) -linear time-
Average case: O(n^2) -quadratic time-
Worst case: O(n^2) -quadratic time-
-
-
-
Selection sort
Simplest sorting techniques, and a good algorithm to sort a small number of elements (an incremental algorithm)
-
It works as follows, First find the smallest element in the list and swap/exchange it with the first position. Then find the second smallest element in the array and swap/exchange it with the second position. Continue in this way until the entire array is sorted.
-
Radix sort
-
-
This sort is unusual because it does not directly compare any of the elements, it is one of the fastest sorting algorithms
is a clever and little sorting algorithm. It puts the elements in order by using the digits of the numbers/values.
-
Searching
Types of search
Linear search
-
time complexity for Unsuccessful search: O(n)
time complexity for successful search:
Best case: O(1)
Worst case: O(n)
Binary search
Useful for large sorted array, 'must sort the array before looking for Skey'
it will use three variables to find Skey -Start, Mid, End-
time complexity for Unsuccessful search: O(log n)
time complexity for successful search:
Best case: O(1)
Average case: O(log n)
worst case: O(log n)
The process of finding a particular element of an array,
if the item is not present in the array, then it's called unsuccessful
-
Recursion
Properties
-
Each time the function does call itself,
control must be closer to base criteria
-
-
