Time Complexity - OpenGenus IQ: Learn Algorithms, DL, System Design (Page 2)

Time and Space Complexity of Heap data structure operations

In this article, we have explored the Time and Space Complexity of Heap data structure operations including different cases like Worst, Average and Best case. At the end, we have added a table summarizes the complexities.

Time Complexity

Time and Space Complexity of Hash Table operations

This article covers Time and Space Complexity of Hash Table (also known as Hash Map) operations for different operations like search, insert and delete for two variants of Hash Table that is Open and Closed Addressing.

Time Complexity

Time & Space Complexity of AVL Tree operations

In this article, we will dive into the Time & Space Complexity and Complexity analysis of various AVL Tree operations like searching, inserting and deleting for different cases like Worst, Best and Average Case.

Time Complexity

Time & Space Complexity of Binary Tree operations

In this article, we will be discussing Time and Space Complexity of most commonly used binary tree operations like insert, search and delete for worst, best and average case.

Time Complexity

Time and Space Complexity of Interpolation Search

In this post, we discuss interpolation search algorithm, its best, average and worst case time complexity and compare it with its counterpart search algorithms. We derive the average case Time Complexity of O(loglogN) as well.

Time Complexity

Time and Space Complexity of Kruskal’s algorithm for MST

In this article, we have explored Time and Space Complexity of Kruskal’s algorithm for MST (Minimum Spanning Tree). We have presented the Time Complexity of different implementations of Union Find and presented Time Complexity Analysis of Kruskal’s algorithm using it.

Time Complexity

Time & Space Complexity of Dijkstra's Algorithm

In this article, we have explored the Time & Space Complexity of Dijkstra's Algorithm including 3 different variants like naive implementation, Binary Heap + Priority Queue and Fibonacci Heap + Priority Queue.

Algorithms

Time & Space Complexity of Merge Sort

In this article, we have explained the different cases like worst case, best case and average case Time Complexity (with Mathematical Analysis) and Space Complexity for Merge Sort. We will compare the results with other sorting algorithms at the end.

Algorithms

Time & Space Complexity of Bellman Ford Algorithm

In this post, we do an analysis the Bellman Ford's single source shortest path graph algorithm to find its computational Time and Space complexity for Best case, Worst case and Average Case.

Time Complexity

Time & Space Complexity of Heap Sort

In this article, we have explained Time & Space Complexity of Heap Sort with detailed analysis of different cases like Worst case, Best case and Average Case.

Time Complexity

Time Complexity of Multiplication

The Brute force Time Complexity of Multiplication operation is O(logM x logM) while the Theoretical limit of Time Complexity of Multiplication operation is O(logM x loglogM) for multiplying number number M x M.

Time Complexity

Time Complexity of Dynamic Array

We have explained Complexity Analysis of Dynamic Array along with Time and Space Complexity of different operations of Dynamic Array.

Time Complexity

Time Complexity Analysis of Linked List

We have presented the Time Complexity analysis of different operations in Linked List. It clears several misconceptions such that Time Complexity to access i-th element takes O(1) time but in reality, it takes O(√N * N) time. We have presented space complexity of Linked List operations as well.

Time Complexity

Time Complexity Analysis of Array

We have presented the Time Complexity analysis of different operations in Array. It clears several misconceptions such that Time Complexity to access i-th element takes O(1) time but in reality, it takes O(√N) time. We have presented space complexity of array operations as well.

Time Complexity

Time Complexity of Addition Operation

We have demonstrated the Time Complexity analysis of Addition operation. It is assumed to take constant time O(1) but it takes linear time O(N) in terms of number of bits. We have presented the space complexity along with implementation of addition using bitwise operations.

Time Complexity

Basics of Time Complexity Analysis [+ notations and Complexity class]

We have explored the Basics of Time Complexity Analysis, various Time Complexity notations such as Big-O and Big-Theta, ideas of calculating and making sense of Time Complexity with a background on various complexity classes like P, NP, NP-Hard and others.

Time Complexity

Time Complexity for non-comparison based Sorting

We have explained why the minimum theoretical Time Complexity of non-comparison based sorting problem is O(N) instead of O(N logN). This is a must read. It will open up new insights.

Time Complexity

Time & Space Complexity of Binary Search [Mathematical Analysis]

We have presented the Mathematical Analysis of Time and Space Complexity of Binary Search for different cases such as Worst Case, Average Case and Best Case. We have presented the exact number of comparisons in Binary Search.

Time Complexity

Time & Space Complexity of Linear Search [Mathematical Analysis]

We have presented the Mathematical Analysis of Time and Space Complexity of Linear Search for different cases such as Worst Case, Average Case and Best Case. We have presented the exact number of comparisons in Linear Search.

Algorithms

Probability of Collision in Hash Function [Complete Analysis]

We present the Mathematical Analysis of the Probability of Collision in a Hash Function. You will learn to calculate the expected number of collisions along with the values till which no collision will be expected and much more.

Algorithms

Why O(1) time complexity does not exist? + Memory Model

We have taken an in-depth look at the operations or algorithms that have a constant time in terms of asymptotic notation of time complexities. Is O(1) really a practical way of representing the time complexity of certain algorithms/ operations?

Algorithms

Time Complexity Bound for comparison based sorting

We have explained the mathematical analysis of time complexity bound for comparison based sorting algorithm. The time complexity bound is O(N logN) but for non-comparison based sorting, the bound is O(N).

Algorithms

Approximate algorithms for NP problems

We have covered Idea of Approximate algorithms for NP problems. NP problems are tough but Approximate algorithms are considered to be a good approach as we get a answer close to the real answer in reasonable time. We have covered the basics with examples of problems like Bin Packing.

Time Complexity

Time and Space complexity of Radix Sort

In this article, we have explained the Time and Space complexity of the radix sort with Mathematical and Intuitive Analysis.

Time Complexity

Time and Space complexity of Quick Sort

We have explained the different cases like worst case, best case and average case Time Complexity (with Mathematical Analysis) and Space Complexity for Quick Sort.