Scribd
Upload
4 views1 page

DSA Quick Revision Notes

This document provides a quick overview of key concepts in data structures and algorithms, including time complexity classifications and specific algorithm complexities such as Quick Sort and Counting Sort. It also covers nested loop complexities, binary tree properties, and important formulas related to hashing and binary search trees. The notes serve as a concise reference for understanding fundamental algorithmic principles.

Uploaded by

vikashchauhan.secl
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
4 views1 page

DSA Quick Revision Notes

This document provides a quick overview of key concepts in data structures and algorithms, including time complexity classifications and specific algorithm complexities such as Quick Sort and Counting Sort. It also covers nested loop complexities, binary tree properties, and important formulas related to hashing and binary search trees. The notes serve as a concise reference for understanding fundamental algorithmic principles.

Uploaded by

vikashchauhan.secl
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

DATA STRUCTURES & ALGORITHMS QUICK NOTES

1. TIME COMPLEXITY BASICS


O(1) - Constant
O(log n) - Logarithmic
O(n) - Linear
O(n log n) - Linearithmic
O(n^2) - Quadratic

2. NESTED LOOP COMPLEXITY


Outer loop i++ -> O(n)
Inner loop j*=2 -> O(log n)
Total -> O(n log n)

3. QUICK SORT
Partition Complexity -> Theta(n)
Best/Average -> O(n log n)
Worst -> O(n^2)

4. COUNTING SORT
T(n) = Theta(n+k)
Counting Sort is Stable
Used in Radix Sort

5. HASHING
Load Factor alpha = n/m

6. BST
TREE-SUCCESSOR Complexity = O(h)

7. BINARY TREE
Maximum nodes = 2^h - 1
Complete => Height Balanced
Height Balanced => Complete (False)

8. ARRAY REPRESENTATION
Left Child = 2i
Right Child = 2i+1
Parent = floor(i/2)

9. IMPORTANT FORMULAS
Counting Sort -> Theta(n+k)
Load Factor -> n/m
BST Successor -> O(h)
Nested Loop -> O(n log n)

You might also like