Category Archives: Analysis of 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 »