- Data Structures and Algorithms
Preface
- Preface
Online Judges
- Why, What and How?
- Popular Online Platforms
- Tearing Down a Problem
Time & Space Complexity
- Inroduction to Time Complexity
- Introduction to Space Complexity
- Different Notations in Time Complexity
- Comparing different time complexities
- How to Calculate Time Complexity?
- Quiz: Time Complexity
Control Flow Practice
- if-else and else-if ladder Practice
- Loops Practice 1
- Loops Practice 2
- Loops Practice 3
- Loops Practice 4
- Square Star and Rhombus Star Patterns
- Triangle Star Patterns
- Pyramid Star Patterns
- Miscellaneous Star Patterns
- Number Patterns 1
- Number Patterns 2
- Triangular Number Patterns 1
- Triangular Number Patterns 2
- Triangular Number Patterns 3
- switch Statement Practice
Arrays Basics
- Coming Soon.
- Array I
- Array II
- Array III
- Array IV
- Array V
- Array VI
String Basics
- Coming Soon.
Matrix Basics
- Coming Soon..
- 2D-Arrays I
- 2D- Arrays II
- 2D-Arrays III
- 2D-Arrays IV
- 2D-Arrays V
Math Basics
- Introduction to Basic Math
- Sum Of Digits of A Number
- Reverse a Number
- Check Palindrome
- Armstrong Number
- Factorial of a Number
- Find the number of trailing zeroes in a given factorial of n
- Modulo Arithmetic
- Divisors of a number
- Divisibility Rules
- Number System
Recursion Basics
- Introduction to Recursion - Understand Recursion by Examples
- Getting a hang of Recursion
- Most Asked Recursion Practice Problems with Solutions
- Fast Exponentiation Algorithm: Efficient Power Calculation Explained
- Find whether a given integer is a power of 3: Power of three
- Recursion: Time & Space Complexity Analysis - 1
- Recursion: Time & Space Complexity Analysis - 2
- Time Complexity Analysis Using Recurrence Relations
- Coming Soon..
Sorting
- Bubble Sort Algorithm
- Selection Sort Algorithm
- Insertion Sort Algorithm
- First Missing Positive
- Merge Sort
- Quick Sort
- Counting Sort
- Comparator Sort
- +5 Problems on Comparator Sort | Code C++/Python/Java
- Largest Number
- Sort the Jumbled Numbers
- Custom Sort String
- Rank Teams by Votes
Two Pointer
- Reverse String
- Merge Strings Alternately
- Minimum Length of String After Deleting Similar Ends
- Merge Two 2D Arrays by Summing Values
- Container with Most Water
- String Compression
- Reverse Prefix of Word
- Separate Black and White Balls
- Merge Sorted Array
- Watering Plants II
- Sort Array By Parity
- Rotate Array
- Sentence Similarity III
- Next Greater Element III
- Next Permutation
- Move Pieces to Obtain a String
Prefix Sum
- Range Sum Query - Immutable
- Subarray Sum Equals K
- Minimum Penalty for a Shop
- Product of Array Except Self
- Sum of Absolute Differences in a Sorted Array
- Find Good Days to Rob the Bank
- Subarray Sums Divisible by K
- Make Sum Divisible by P
- Removing Minimum Number of Magic Beans
- Product of the Last K Numbers
- Count Number of Bad Pairs
- Continuous Subarray Sum
- Count of Interesting Subarrays
- Movement of Robots
- Find All Good Indices
- Count Number of Nice Subarrays
- Maximum Population Year
- Points That Intersect With Cars
- Pongal Bunk
- Car Pooling
- Shifting Letters II
- My Calendar II
- Left and Right Sum Differences
Matrix
- Rotate Image
- Convert 1D Array Into 2D Array
- Row with Maximum ones
- Richest Customer Wealth
- Set Matrix Zeroes
- Queens That Can Attack The King
- Modify the Matrix
- Matrix Diagonal Sum
- Lucky Number in a Matrix
- Check if Matrix Is X-Matrix
- Transpose Matrix
- Spiral Matrix
- Prime In Diagonal
- Maximum Matrix Sum
- Largest Local Values in a Matrix
- Spiral Matrix II
Hashing
- Subarray Sum Equals K
- First Missing Positive
- Isomorphic Strings
- Find Common Elements Between Two Arrays
- Majority Element
- Majority Element II
- Contains Duplicate
- Subarray Sums Divisible by K
- Make Sum Divisible by P
- Count Number of Bad Pairs
- Continuous Subarray Sum
- Count of Interesting Subarrays
- Count Number of Nice Subarrays
- Sum of Unique Elements
- Optimal Partition of String
- Groups of Special-Equivalent Strings
- Word Subsets
- Find the Maximum Number of Elements in Subset
- People Whose List of Favorite Companies Is Not a Subset of Another List
- Custom Sort String
- Count the Number of Good Partitions
- Count Beautiful Substrings II
Sliding Window
- Maximum Number of Occurrences of a Substring
- Longest Substring Without Repeating Characters
- Count the Number of Substrings With Dominant Ones
- Minimum Size Subarray Sum
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
- Longest Repeating Character Replacement
- Max Consecutive Ones III
- Substrings of Size Three with Distinct Characters
- Minimum Window Substring
- Substring with Concatenation of All Words
Linked List
Stack
- Next Greater Element I
- Merge Intervals
- Insert Interval
- Valid Parentheses
- Asteroid Collision
- Minimum Add to Make Parentheses Valid
- Minimum Remove to Make Valid Parentheses
- Coming Soon..
- Maximum Nesting Depth of the Parentheses
- Reverse Substrings Between Each Pair of Parentheses
- Remove Outermost Parentheses
- Check if a Parentheses String Can Be Valid
- Min Stack
- Maximum Frequency Stack
- Score of Parentheses
- Dinner Plate Stacks
Queue
- Coming Soon..
Binary Search
- Coming Soon..
- Binary Search Algorithm Solution: Iterative & Recursive Ways
- Sqrt(x) LeetCode Solution | Approaches in C++/Java/Python
- Find Peak Element LeetCode Solution | Code in C++/Java/Python
- Find Minimum in Rotated Sorted Array Solution In C++/Java/Python
- Find Peak Index in a Mountain Array Solution | Code In C++/Java/Python
- Search in rotated sorted array leetcode solution | Code In C++/Python/Java
- Maximum Value at a Given Index in a Bounded Array Solution
- Most Profit Assigning Work Leetcode Solution
- Maximum Candies Allocated to K Children Solution
- Aggressive Cows Leetcode Solution
- Maximum Side Length of a Square with Sum Less than or Equal to Threshold
- Minimum Speed to Arrive on Time
- Minimum time to repair cars Solution In C++/Python/Java
- Maximum Number of Removable Characters Solution in C++/Java/Python
- Heaters Leetcode Solution In C++/Python/Java
- Earliest Second to Mark Indices I Solution In C++/Python/Java
- Maximum White Tiles Covered by a Carpet Solution In C++/Python/Java
- Minimum Absolute Difference Between Elements With Constraint Solution In C++/Python/Java
- Sell Diminishing-Valued Colored Balls Solution In C++/Python/Java
- Ugly Number III Solution In C++/Python/Java/JS
- Minimize the Maximum of Two Arrays Solution in C++/Java/Python/JS
- Find a Peak Element II Solution In C++/Java/Python/JS
- Guess Number Higher or Lower Solution In C++/Java/Python/JS
Bit Manipulation
- Coming Soon..
Recursion and Backtracking
- Coming Soon..
Trees
- Coming Soon..
Heaps
- Coming Soon..
Tries
- Coming Soon..
Greedy
- Maximum 69 Number
- Maximum Sum With Exactly K Elements
- Minimum Time to Type Word Using Special Typewriter
- Minimum Operations to Make the Array Increasing
- Minimum Number of Operations to Convert Time
- Lemonade Change
- Assign Cookies
- Minimum Cost to Move Chips to The Same Position
Dynamic Programming
Graphs
- Coming Soon..
String Matching Algorithms
Combinatorics
Geometry
Game Theory
Advanced Algorithm

Time & Space Complexity

Comparing different time complexities

In this article, I'll try to give you folks a brief idea about how much time codes with different time complexities take to run when given different sizes of inputs.

Before diving in, I'd like to share that a C++ code can run around 2∗10⁸ operations per second if those are low-level operations (array accesses, additions, bit-shifts, multiplies, subtractions, xors, etc.). Mods and divisions are slightly slower. Taking input & printing output is slightly even slower.

Of course, the number of operations per second depends on the machine, but the above-shared number is just a bare minimum that you can safely assume.

For example, my M2 Pro 14" Macbook Pro (subtle flex 😉) was able to run the code below in just less than 0.1 sec.

C++ Code

#include<bits/stdc++.h>
using namespace std;

int main()
{
	clock_t start, end;

	int N = 2e8; // 2e8 means 2*10^8
    int random = 0;

	start = clock();

	for (int i = 1; i <= N; ++i) {
		random++;
	}

	end = clock();

	double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
	cout << "Time taken by program is : " << fixed
	     << time_taken << setprecision(5) << '\n';

	return 0;
}

The ones marked Out of Syllabus were literally trillions of times the curent age of the universe. So, I hope it's okay not to calculate them xD

Conclusion

This article (especially the table above) can be used as a reference for you to decide, based on the time limit and the constraints what time complexity you should target to get that green tick - ✅

Join Our Course

Offer ends in:

Days

Hours

Mins

Secs

Previous - Time & Space Complexity Different Notations in Time Complexity

Next - Time & Space Complexity How to Calculate Time Complexity?

Join Our Course

Offer ends in:

Days

Hours

Mins

Secs

Preface

Online Judges

Time & Space Complexity

Control Flow Practice

Arrays Basics

String Basics

Matrix Basics

Math Basics

Recursion Basics

Sorting

Two Pointer

Prefix Sum

Matrix

Hashing

Sliding Window

Linked List

Stack

Queue

Binary Search

Bit Manipulation

Recursion and Backtracking

Trees

Heaps

Tries

Greedy

Dynamic Programming

Graphs

String Matching Algorithms

Combinatorics

Geometry

Game Theory

Advanced Algorithm