Runtime Analysis of Algorithms

Introduction of Algorithms

The word Algorithm means “A set of rules to be followed in calculations or other problem-solving operations” Or “A procedure for solving a mathematical problem in a finite number of steps that frequently involves recursive operations “....

Asymptotic Analysis

Given two algorithms for a task, how do we find out which one is better?...

Measurement of Complexity of an Algorithm (Worst, Best and Average Case)

Based on the above three notations of Time Complexity there are three cases to analyze an algorithm:...

How to Analyse Loops for Complexity Analysis of Algorithms?

Constant Time Complexity O(1):...

How to combine the time complexities of consecutive loops?

When there are consecutive loops, we calculate time complexity as a sum of the time complexities of individual loops....

Algorithms Cheat Sheet for Complexity Analysis:

Algorithm Best Case Average Case Worst Case Selection Sort O(n^2) O(n^2) O(n^2) Bubble Sort O(n) O(n^2) O(n^2) Insertion Sort O(n) O(n^2) O(n^2) Tree Sort O(nlogn) O(nlogn) O(n^2) Radix Sort O(dn) O(dn) O(dn) Merge Sort O(nlogn) O(nlogn) O(nlogn) Heap Sort O(nlogn) O(nlogn) O(nlogn) Quick Sort O(nlogn) O(nlogn) O(n^2) Bucket Sort O(n+k) O(n+k) O(n^2) Counting Sort O(n+k) O(n+k) O(n+k)...

Runtime Analysis of Algorithms:

In general cases, we mainly used to measure and compare the worst-case theoretical running time complexities of algorithms for the performance analysis. The fastest possible running time for any algorithm is O(1), commonly referred to as Constant Running Time. In this case, the algorithm always takes the same amount of time to execute, regardless of the input size. This is the ideal runtime for an algorithm, but it’s rarely achievable. In actual cases, the performance (Runtime) of an algorithm depends on n, that is the size of the input or the number of operations is required for each input item. The algorithms can be classified as follows from the best-to-worst performance (Running Time Complexity):...

Little o and Little omega notations:

Little-o: Big-O is used as a tight upper bound on the growth of an algorithm’s effort (this effort is described by the function f(n)), even though, as written, it can also be a loose upper bound. “Little-o” (o()) notation is used to describe an upper bound that cannot be tight....

What does ‘Space Complexity’ mean?

The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct definitions of Auxiliary Space and Space Complexity....

Previous Year GATE Questions:

1. What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order? More than one answer may be correct. [GATE CSE 2020] (A) Θ(n) (B) Θ(n log n) (C) Θ(n2) (D) Θ(1) Solution: Correct answer is (C)...