Data Structures & Algorithms (DSA) & Database Management System (DBMS)

🧱 Data Structures

Linear Data Structures

#	Data Structure	Access	Insertion	Deletion	Searching
1️⃣	🧮 Array	⚡ O(1)	⏳ At 0 Index: O(n)	⏳ At 0 Index: O(n)	🔍 Linear: O(n)Binary (Sorted): O(log n)
2️⃣	🔗 Linked List	⏳ O(n)	⚡ O(1)	⚡ O(1)	🔍 O(n)
3️⃣	📚 Stack	⏳ O(n)	⚡ O(1)	⚡ O(1)	🔍 O(n)
4️⃣	🚶 Queue	⏳ O(n)	⚡ O(1)	⚡ O(1)	🔍 O(n)

🌲 Non-Linear Data Structures

#	Data Structure	Access	Insertion	Deletion	Searching	Space
1️⃣	🌿 AVL Tree	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	💾 O(n)
2️⃣	🌳 Binary Search Tree (BST)	🐢 O(n)	🐢 O(n)	🐢 O(n)	🐢 O(n)	💾 O(n)
3️⃣	🌴 B-Tree	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	💾 O(n)
4️⃣	📐 Cartesian Tree	N/A	⏳ O(n)	⏳ O(n)	⏳ O(n)	💾 O(n)
5️⃣	📊 KD Tree	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	💾 O(n)
6️⃣	🔴 Red-Black Tree	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	💾 O(n)
7️⃣	🪜 Skip List / Skip Tree	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	💾 O(n)
8️⃣	🌀 Splay Tree	⚖️ Amortized O(log n)	⚖️ Amortized O(log n)	⚖️ Amortized O(log n)	⚖️ Amortized O(log n)	💾 O(n)
9️⃣	⛰️ Binary Heap	⏳ O(log n)	⚡ O(log n)	⏳ O(log n)	🔍 O(n)	💾 O(n)
🔟	🧩 Hash Table	❌ N/A	⚡ O(1)	⚡ O(1)	⚡ O(1)	💾 O(n)

Note:

H = log n for self-balancing BSTs such as AVL, Red-Black, and Splay Trees — they maintain a logarithmic height.

🧠 Other Advanced Structures

#	Data Structure	Access	Insertion	Deletion	Searching	Space
1️⃣	🕸️ Graph	O(1) (Adj. Matrix)O(V + E) (Adj. List)	⚡ O(1)	⏳ O(V + E)	🔍 O(V + E)	💾 O(V + E)
2️⃣	🔤 Trie	⏳ O(L)	⏳ O(L)	⏳ O(L)	⏳ O(L)	💾 O(ALPHABET_SIZE × n)
3️⃣	📏 Segment Tree	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	⚡ O(log n)	💾 O(n)
4️⃣	🧬 Suffix Tree	⚡ O(n)	⚡ O(n)	⚡ O(n)	⚡ O(m)	💾 O(n)

📈 Asymptotic Notations / Landau Notation (Edmund Landau)

Measures the order of growth of an algorithm with respect to the number of inputs n.

Big O

Represents the worst-case scenario, where the loop runs till the last element.

• Simplified Worst case when loop runs till the last elements:
  • Fastest growing expression determine over all complexity.
  • Remove Constant & Remove non-dominant terms

Example.

f(n) = An+B
= O(n)

f(n) = n3+n2+7n
= O(n3)

Common used big O notation

Complexity	Visual Growth	Description
O(1)	🟢	Constant — fastest, independent of n
O(log n)	🟢🟢	Logarithmic — grows slowly, e.g., Binary Search
O(n)	🟡🟡🟡	Linear — grows proportionally to input size
O(n log n)	🟡🟡🟡🟡	Polylogarithmic — e.g., Merge Sort, Quick Sort (average)
O(n²)	🔴🔴🔴🔴	Quadratic — nested loops, e.g., Bubble Sort
O(n³)	🔴🔴🔴🔴🔴	Cubic — triple nested loops
O(cⁿ)	🔴🔥	Exponential — runtime doubles/triples with each input
O(n!)	🔥🔥🔥	Factorial — extremely fast growth, e.g., brute-force permutations

🟢 1. Optimized (Lower Growth Order)

O(1) - Constant time

• Single R/W
• Single statement of code
• No loops
• A loop which run in fix number of time

O(log(n)) - Logarithmic

• Loop divided by constant number eg Binary Serach
• Divide & conqure

O(n(log(n)) - PolyLogarithmic

• Loop divided & multiplied by constant number

🔴 2. Not Optimized (Higher Growth Order)

Complexity	Type	Description
O(n)	Linear	Loop increases/decreases by constant number
O(nᶜ)	Polynomial	C nested loops
O(n²)	Quadratic	2 nested loops
O(n³)	Cubic	3 nested loops
O(cⁿ)	Exponential	For each element run C nested loops
O(n!)	Factorial	Adds a loop for every element

Notes:

• O(cⁿ) grow faster than O(nᶜ). If O(nᶜ) grow faster than O(cⁿ) than it is called superpolynomial & in that case O( cⁿ) called subexponential

---

⚡ Sorting Algorithm Complexity

Legend

• Ω (Omega) → Best case
• Θ (Theta) → Average case
• O (Big O) → Worst case
• Stable? ✅ Yes / ❌ No

#	Algorithm	⏱️ Best	⚖️ Average	🔻 Worst	💾 Space	⚙️ Stability
1️⃣	⚡ Quick Sort	Ω(n log n)	Θ(n log n)	O(n²)	O(log n)	❌ No
2️⃣	🧩 Merge Sort	Ω(n log n)	Θ(n log n)	O(n log n)	O(n)	✅ Yes
3️⃣	🚀 Timsort	Ω(n)	Θ(n log n)	O(n log n)	O(n)	✅ Yes
4️⃣	⛰️ Heap Sort	Ω(n log n)	Θ(n log n)	O(n log n)	O(1)	❌ No
5️⃣	💧 Bubble Sort	Ω(n)	Θ(n²)	O(n²)	O(1)	✅ Yes
6️⃣	✍️ Insertion Sort	Ω(n)	Θ(n²)	O(n²)	O(1)	✅ Yes
7️⃣	🪞 Selection Sort	Ω(n²)	Θ(n²)	O(n²)	O(1)	❌ No
8️⃣	🌲 Tree Sort	Ω(n log n)	Θ(n log n)	O(n²)	O(n)	✅ Yes
9️⃣	🐚 Shell Sort	Ω(n log n)	Θ(n (log n)²)	O(n (log n)²)	O(1)	❌ No
🔟	🪣 Bucket Sort	Ω(n + k)	Θ(n + k)	O(n²)	O(n)	✅ Yes
1️⃣1️⃣	🔢 Radix Sort	Ω(n k)	Θ(n k)	O(n k)	O(n + k)	✅ Yes
1️⃣2️⃣	🧮 Counting Sort	Ω(n + k)	Θ(n + k)	O(n + k)	O(k)	✅ Yes
1️⃣3️⃣	🧊 Cube Sort	Ω(n)	Θ(n log n)	O(n log n)	O(n)	✅ Yes

---

🔎 Searching Algorithm Complexity

#	Algorithm	⏱️ Best	⚖️ Average	🔻 Worst	💾 Space	⚙️ Stability
1️⃣	🚶‍♂️ Linear Search	O(1)	O(n)	O(n)	O(1)	✅ Yes
2️⃣	🎯 Binary Search	O(1)	O(log n)	O(log n)	O(1)	✅ Yes
3️⃣	🪜 Jump Search	O(1)	O(√n)	O(√n)	O(1)	✅ Yes
4️⃣	🧩 Interpolation Search	O(1)	O(log log n)	O(n)	O(1)	✅ Yes
5️⃣	⚡ Exponential Search	O(1)	O(log n)	O(log n)	O(1)	✅ Yes
6️⃣	🧮 Fibonacci Search	O(1)	O(log n)	O(log n)	O(1)	✅ Yes
7️⃣	🔢 Hashing Search	O(1)	O(1)	O(n)	O(n)	✅ Yes
8️⃣	🌳 Binary Search Tree (BST)	O(1)	O(log n)	O(n)	O(n)	✅ Yes
9️⃣	🌲 Balanced BST (AVL, Red-Black)	O(1)	O(log n)	O(log n)	O(n)	✅ Yes

Notes

• Binary Search requires sorted data.
• Hashing gives average constant-time lookup but degrades to O(n) on collisions.
• Balanced Trees ensure logarithmic performance by maintaining structure.
• Jump and Interpolation searches are useful for uniformly distributed data.

---

🗄️ Database Comparison

DB	Paradigm	Key Features	Use Case / Space / Notes
Redis	🔑 Key-Value	In-Memory, PUB/SUB, Caching	Leaderboards, Session Storage 🟢
Cassandra	🟩 Wide Column	Schema-less, No Joins	High write throughput, Time Series ⏱️
HBase	🟩 Wide Column	Schema-less, No Joins	Large-scale storage, Batch Processing 🟡
MongoDB / Firebase / CouchDB / Dynamo	📄 Document-Oriented	Schema-less, No Joins	IOT, Games, Fast Reads & Writes 🎮
MySQL (Oracle) / PostgreSQL	🗂️ Relational	Schema, Join, ACID	Banking, Enterprise Applications 🏦
Neo4J	🌐 Graph	Relationships, Graph Queries	Knowledge Graphs, Recommendations 🌐
Solr / Algolia / Elasticsearch	🔎 Search Index	Indexing, Full-text Search	Search Engines 🔍
Fauna / GraphQL	⚡ Multi-Model	Flexible, Multi-paradigm	Modern APIs, Not restricted to one model ⚡