Scribd
Upload
4 views2 pages

Data Structures Algorithms Notes

The document provides comprehensive study notes on Data Structures and Algorithmic Complexity, focusing on asymptotic analysis and Big-O notation, which categorizes algorithm performance. It compares core data structures like arrays, linked lists, hash tables, and binary search trees, highlighting their time complexities. Additionally, it outlines fundamental graph algorithms such as BFS, DFS, and Dijkstra's Algorithm, detailing their traversal methods and time complexities.

Uploaded by

Justin Paul Vallinan
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 views2 pages

Data Structures Algorithms Notes

The document provides comprehensive study notes on Data Structures and Algorithmic Complexity, focusing on asymptotic analysis and Big-O notation, which categorizes algorithm performance. It compares core data structures like arrays, linked lists, hash tables, and binary search trees, highlighting their time complexities. Additionally, it outlines fundamental graph algorithms such as BFS, DFS, and Dijkstra's Algorithm, detailing their traversal methods and time complexities.

Uploaded by

Justin Paul Vallinan
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

COMPREHENSIVE STUDY NOTES • COMPUTER SCIENCE

Data Structures & Algorithmic Complexity

1. Asymptotic Analysis & Big-O Notation

Asymptotic analysis characterizes the execution time or space requirement of an algorithm as the input size n grows
toward infinity. Big-O (O) provides an upper bound on worst-case performance.

Notation Complexity Class Canonical Example Algorithm

O(1) Constant Hash Table lookup, Array indexing

O(log n) Logarithmic Binary Search in sorted array

O(n) Linear Linear Search, Unsorted list traversal

O(n log n) Linearithmic Merge Sort, Quick Sort (average case), Heap Sort

O(n²) Quadratic Bubble Sort, Insertion Sort, Selection Sort

O(2ⁿ) Exponential Recursive Fibonacci without memoization

2. Core Data Structures

Abstract Data Type Comparison


• Arrays vs. Linked Lists: Arrays offer O(1) random access but O(n) insertion/deletion. Linked lists offer O(1)
insertion at known pointers but O(n) sequential access.
• Hash Tables: Utilize a hash function to map keys to bucket indices, yielding O(1) average time complexity for
insertion, deletion, and lookup. Collision resolution: Chaining vs. Open Addressing.
• Binary Search Trees (BST): Balanced trees (AVL, Red-Black) guarantee O(log n) time for search, insertion,
and deletion by maintaining height balance factors.

3. Fundamental Graph Algorithms

Graphs G = (V, E) model complex relational data. Primary traversal and pathfinding paradigms include:

Breadth-First Search (BFS)


Uses a First-In-First-Out (FIFO) queue to explore graph level-by-level. Computes shortest path on unweighted graphs in
O(|V| + |E|) time complexity.

Depth-First Search (DFS)


Uses a Last-In-First-Out (LIFO) stack (or call stack recursion) to explore paths deeply before backtracking.
Fundamental for topological sorting and strongly connected components.
Dijkstra's Algorithm
Determines single-source shortest paths on weighted non-negative graphs. Utilizing a min-priority heap, execution time
is O((|V| + |E|) log |V|).

Educational Notes Series • Theoretical Computer Science • Page 1

You might also like