Category Archives: Algorithm

Time Complexity of building a heap

Time Complexity of building a heap If you don’t know what is a heap, and how it is build, then we recommend you go through the whole article, else you can directly skip to the last part which explains the complexity. A heap is a complete binary tree that satisfies the heap property. A heap… Read More »

Space Complexity

Space Complexity and Auxiliary Space Auxiliary Space is the extra space or temporary space used by an algorithm. Eg: Space taken up by an extra variable used for swapping purposes in a function that swaps the values of two variables.  Space Complexity of an algorithm is total space taken by the algorithm with respect to the input… Read More »

Asymptotic Notation

Asymptotic Notation Asymptotic Notation Video Explanation:   The following 3 asymptotic notations are mostly used to represent time complexity of algorithms. Big-Oh Notation Big-Oh notation is a convenient way to express the worst-case scenario of a given algorithm. This is the most used notation any programmer will come across. Mathematically, we say that f(n) = O(g(n)) when… Read More »

Analysis of Loops

Asymptotic Analysis of Loops We begin this section with some examples. Constant Time: O(1) Time complexity of a function or a set of statements is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function. Consider the swap() function: /*This functions is used to swap two numbers*/ void… Read More »

Worst, Best and average case

Worst, Average and Best Cases of an algorithm We can have three cases to analyze an algorithm: Worst Case Worst case analysis gives us the longest running time of any algorithm. This may also be framed as: Worst Case analysis gives us an upper bound on running time. Consider linear search in an array of size… Read More »

Asymptotic Analysis

Asymptotic Analysis Need to analyze algorithms? To efficiently code up a certain problem we need to estimate the time and space requirement of the algorithms that have been developed before implementing them. Analysing algorithms allows you to answer questions such as: Time Complexity: How long will a program run on an input? Space Complexity: How much… Read More »

Insertion Sort

Insertion Sort In Insertion Sort, we grow the sorted array one element at a time. The array is divided into two parts, sorted part and unsorted part, sorted part being the part we have already traversed i. e. to the left of current index. At this point, it’d be well to mention that a single number… Read More »

Bubble Sort

Bubble Sort Bubble Sort (for ascending order) can be seen as the following steps: Algorithm for Bubble Sort: Traverse the given array n = size of array times. Compare adjacent elements of the array. If they are in the wrong order i.e. in descending order then swap them as we want the elements to be in… Read More »

Selection Sort

Selection Sort Selection Sort (for sorting in ascending order) can be seen as the following steps: Algorithm for Selection sort: Find the smallest element in the array. Put the element at the beginning of the array. Continue the steps 1 and 2 by incrementing the starting point in each iteration. The array is divided into… Read More »

Matrix Chain Multiplication

Matrix Chain Multiplication – Dynamic Programming Matrix Chain Multiplication Problem Statement: Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain. The problem… Read More »