Scribd
Upload
5 views1 page

Algorithm Complexities

This cheat sheet provides a concise overview of various algorithms along with their time and space complexities. It covers basic operations, decision-making structures, and specific algorithms such as the Segmented Sieve, Quick Sort, and N-Queens. Each entry lists the algorithm's time complexity and space complexity, highlighting their efficiency and resource requirements.

Uploaded by

sadiazoyasyed
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views1 page

Algorithm Complexities

This cheat sheet provides a concise overview of various algorithms along with their time and space complexities. It covers basic operations, decision-making structures, and specific algorithms such as the Segmented Sieve, Quick Sort, and N-Queens. Each entry lists the algorithm's time complexity and space complexity, highlighting their efficiency and resource requirements.

Uploaded by

sadiazoyasyed
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithms Time & Space Complexity Cheat Sheet

1. Basic I/O, Operators – Time: O(1), Space: O(1)


2. Decision Making & Control Structures – Time: O(1) to O(n), Space: O(1)
3. Introduction to Algorithms – Depends on algorithm
4. Time & Space Complexity – Theoretical topic
5. Segmented Sieve – Time: O((R-L+1) + √R log log √R), Space: O(R-L+1)
6. Incremental Sieve – Time: O(N log log N), Space: O(N)
7. Euler’s Phi Algorithm – Time: O(√n), Space: O(1)
8. Remainder Theorem – Time: O(log n), Space: O(1)
9. Strobogrammatic Number – Time: O(n), Space: O(1)
10. Binary Palindrome – Time: O(log n), Space: O(1)
11. Booth’s Algorithm – Time: O(n), Space: O(1)
12. Euclid’s Algorithm – Time: O(log(min(a,b))), Space: O(1)
13. Karatsuba Algorithm – Time: O(n^1.585), Space: O(n)
14. Longest Sequence of 1 After Flip – Time: O(n), Space: O(1)
15. Swap Two Nibbles – Time: O(1), Space: O(1)
16. Block Swap Algorithm – Time: O(n), Space: O(1)
17. Max Product Subarray – Time: O(n), Space: O(1)
18. Maximum Hourglass Sum – Time: O(n^2), Space: O(1)
19. Max Equilibrium Sum – Time: O(n), Space: O(1)
20. Leaders in Array – Time: O(n), Space: O(1)
21. Majority Element – Time: O(n), Space: O(1)
22. Quick Sort – Avg: O(n log n), Worst: O(n^2), Space: O(log n)
23. Selection Sort – Time: O(n^2), Space: O(1)
24. Weighted Substring – Time: O(n), Space: O(1/n)
25. Move Hyphen – Time: O(n), Space: O(1)
26. Manacher’s Algorithm – Time: O(n), Space: O(n)
27. Sorted Unique Permutation – Time: O(n × n!), Space: O(n)
28. Maneuvering – Exponential, backtracking, Space: O(n)
29. Combination – Time: O(k × C(n,k)), Space: O(k)
30. Josephus Trap – Time: O(n), Space: O(1)
31. Maze Solving – Time: O(N×M), Space: O(N×M)
32. N-Queens – Time: O(N!), Space: O(N)
33. Activity Selection – Time: O(n log n), Space: O(1)

You might also like