DS Module 2: Linked Lists and Analysis of Algorithms

Recursion

repetition where a funct calls itself until base case.

Base Case

condition that stop repetition in recursive.

Factorial (Recursive Formula)

If n > 0, n! = n * (n-1)!; if n = 0, 0! = 1.

Recursive Trace

visualization technique to track recursive calls and value

Recursive Linear Sum

method where sum of n int is calculated as LinearSum(A, n-1) + A[n-1]

Linear Fibonacci

recursive algorithm with only k-1 calls, avoiding redundant operations

Constant Function

f(n) = c; no of operations independent of input size n

Logarithm Function

f(n) = log_b(n), commonly base 2 in cs

Log Rule 1 (Product)

log(ac) = log(a) + log(c).

Log Rule 2 (Quotient)

log(a/c) = log(a) - log(c).

Log Rule 3 (Power)

log(a^c) = c * log(a).

Linear Function

f(n) = n; represents runtime of single loop through n elem

N-Log-N Function

f(n) = n * log(n); grows slight faster than linear but slower than quadratic.

Quadratic Function

f(n) = n^2; runtime of nested loops (n * n iterations).

Growth Rate

how running time inc as input size n grows

Big O (Upper Bound)

f(n) is O(g(n)) if f(n) <= c * g(n) for all n >= n0.

Big Omega (Lower Bound)

f(n) is Ω(g(n)) if f(n) >= c * g(n) for all n >= n0.

Big Theta (Tight Bound)

f(n) is Θ(g(n)) if it's bounded above and below by g(n).

Reflexivity (Big O)

property that any function f is O(f).

Transitivity (Big O)

If f = O(g) and g = O(h), then f = O(h).

Sums Rule (Big O)

If f1 = O(g1) and f2 = O(g2), then f1 + f2 = O(max{g1, g2}).

Asymptotic Simplification

keeping only highest-order term

Hidden Constants

Factors ignored in Big O that may make an O(n) algorithm slower than O(n log n) in practice.

Array Shifting Inefficiency

Add/remove in large arrays is O(n) bc many elem may be shifted.

Linked List

A ds made of chain of nodes with elem and pointers.

Node

An object that stores elem and >1 pointer to another node.

Singly Linked List

chain of nodes with each having only 1 "next" pointer.

Head and Tail

The "head" first node. "tail" last node and "next" points to NULL.

Friend Keyword (Linked Lists)

Allow LinkedList class to access private members of Node class.

DLL Sentinels

Special dummy nodes (header and trailer) that simplify list operations.

DLL Deletion Logic

Updating adjacent nodes to bypass target node

Circularly Linked List

last node points back to first node instead of NULL.

Circular List advance()

A method that moves the cursor to the next node in the circular chain.