ALGORITHMS

 I’m making this for my quick reference for what I learned from the video series below and other sources.

My C Playlist (In Malayalam):

Time Complexity:

Types of Time Functions:

Time Complexities Cheat Sheet:

Time Complexities of all Sorting Algorithms:

Divide and Conquer:

Recurrence Relation:

Masters Theorem For Decreasing Functions:

Masters Theorem For Division Functions:

ROOT FUNCTION:

Binary search Time Complexity:

Iterative method:

Heap: (heap is a complete binary tree)

Theoretically, index is taken from 1 to make I easy to explain but in programming the index is taken from 0.

The positions are left blank to follow the rules. The 3rd binary tree is not a complete binary tree, because even if there is a single missing element in between when represented as an array it is not a complete binary tree(Note* Elements are filled from left to right in a binary tree). So 2nd one is a complete binary tree.

Height of a binary tree: log n

Min Heap & Max Heap:

Inserting element in a heap:

Here, number of swaps = height of binary tree => O(log n)

Delete an element from the heap: click for the timestamp

Heap sort:

When deleting, the root elements are deleted in a heap. So, by adding the deleted elements to the empty space thus sorts the elements.

Heap sort takes: O(n log n)

HEAPIFY: O(n)

Creating a normal heap: O(n log n)

[Note* this is the time for creating not adding / deleting which is: O(log n) ]

Priority queue:

Heap data structure is faster when implementing Priority queue.

Time: O(log n), when deleting &, O(log n), when inserting.

2-way merge sort: O(n log n )

2-way merge sort is iterative and merge sort is recursive.

Merge sort: O(n log n )

Merge sort is in-place sort in the case of a linked list not in the case of an array

Quick Sort:

Strassen’s Matrix Multiplication:

Above formula time complexity: O(n³)

Strassen reduced it to: O(n^(2.81))

Greedy method:

Used for solving optimization problems (problems that require either minimum results or maximum results).

A solution that satisfies the condition in the problem is a feasible solution.

HASHING

To avoid collision there are several methods:

Chaning:

Linear Probing: f(i)=i ; i=0,1,2,…

This causes the clustering of elements so quadrating probing is introduced

Quadrating Probing: f(i)=i² ; i=0,1,2,…

Hash map: