Scribd
Upload
2 views1 page

Algorithm Complexity Cheat Sheet

This document provides a comprehensive cheat sheet on algorithm complexity, detailing various time and space complexities for different types of loops and recursive functions. Key complexities include O(n) for single loops, O(n^2) for nested loops, and O(n log n) for divide and merge algorithms. It also covers complexities for operations like binary search and hash map operations.

Uploaded by

leitegcc
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
2 views1 page

Algorithm Complexity Cheat Sheet

This document provides a comprehensive cheat sheet on algorithm complexity, detailing various time and space complexities for different types of loops and recursive functions. Key complexities include O(n) for single loops, O(n^2) for nested loops, and O(n log n) for divide and merge algorithms. It also covers complexities for operations like binary search and hash map operations.

Uploaded by

leitegcc
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

Algorithm Complexity Cheat Sheet

1. Single Loops: O(n) time, O(1) space.


2. Constant Loops: O(1) time, O(1) space.
3. Nested Loops (full range): O(n^2) time.
4. Triangular Loops: O(n^2) time.
5. Sum of Squares: O(n^3) time.
6. Mixed with log(n): O(n log n).
7. Logarithmic Loops: O(log n).
8. Geometric Growth Inner Loops: O(n).
9. Harmonic Inner Loops: O(n log n).
10. Variable Inner log(i): O(n log n).
11. Mixed Ranges (i..n): O(n^2).
12. Linear Recursion: O(n) time, O(n) space.
13. Binary Division Recursion: O(log n) time, O(log n) space.
14. Two Halves Recursion: O(n) time, O(log n) space.
15. Divide & Merge: O(n log n) time.
16. Exponential Tree Recursion: O(2^n) time.
17. Branching b: O(b^n).
18. Multiple smaller calls: exponential.
19. Array creation: O(n) time/space.
20. Matrix creation: O(n^2) time/space.
21. Hash map ops: O(1) avg.
22. Binary search: O(log n).
23. Write array: O(n).
24. Adjacent loops: O(n).
25. Loop with O(1) work: O(n).

You might also like