NAPT cheat sheet

Time complexity of binary search: O(log n) for a sorted array; worst-case comparisons = floor(log2 n) + 1.

Hash table average-case lookup is O(1); worst-case O(n) when all keys collide; load factor α = n/m; open addressing requires α < 1.

A stable sort preserves the relative order of equal elements: insertion sort, merge sort, and counting sort are stable; quicksort and heapsort are not stable in their standard forms.

Big-O defines an asymptotic upper bound: f(n) = O(g(n)) if there exist constants c > 0 and n0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0.

Binary search tree in-order traversal yields keys in ascending order; search, insert, and delete are O(h) where h is tree height (O(log n) if balanced, O(n) if degenerate).

Dynamic array amortized append is O(1); a single append that triggers resizing is O(n) because it copies all existing elements.

Queue is FIFO (enqueue at rear, dequeue from front); stack is LIFO (push and pop at top); both support O(1) push/pop in linked or array implementations.

Dijkstra's algorithm requires non-negative edge weights; with a binary heap its complexity is O((V+E) log V).

Single Responsibility Principle: a class should have only one reason to change, meaning one actor or stakeholder it serves.

Open/Closed Principle: software entities should be open for extension but closed for modification; achieved via abstraction and polymorphism.

Liskov Substitution Principle: objects of a superclass should be replaceable with objects of a subclass without altering correctness of the program.

Interface Segregation Principle: clients should not be forced to depend on interfaces they do not use; prefer many small interfaces over one large interface.

Dependency Inversion Principle: high-level modules should not depend on low-level modules; both should depend on abstractions, and abstractions should not depend on details.

Layered architecture restricts dependencies to adjacent layers (presentation → business → persistence); a layer may call only the layer directly below it.

Coupling measures interdependence between modules; cohesion measures relatedness within a module; good design aims for low coupling and high cohesion.

The Model-View-Controller pattern separates data/model, presentation/view, and input handling/controller to isolate changes and enable independent testing.

First normal form (1NF) requires atomic column values and no repeating groups; each row-column intersection holds a single value.

Second normal form (2NF) requires 1NF and no partial dependency: every non-key attribute must depend on the whole primary key, not part of a composite key.

Third normal form (3NF) requires 2NF and no transitive dependency: non-key attributes must not depend on other non-key attributes.

ACID: Atomicity (all-or-nothing), Consistency (valid state transitions), Isolation (concurrent transactions do not interfere), Durability (committed changes survive failure).

SQL join types: INNER JOIN returns matching rows only; LEFT JOIN returns all left rows plus matches; FULL OUTER JOIN returns all rows from both sides with NULLs where unmatched.

A foreign key enforces referential integrity: values in the child column must exist in the parent key or be NULL (if nullable).

GROUP BY collapses rows into groups; HAVING filters groups after aggregation, whereas WHERE filters individual rows before aggregation.

A database index speeds up SELECT lookups and ORDER BY but adds write overhead and storage; a composite index is usable only when the query filters on a leftmost prefix of its columns.

Black-box testing derives test cases from specifications without knowledge of internal code; equivalence partitioning and boundary value analysis are core techniques.

Boundary value analysis tests values at, just below, and just above each boundary (e.g., min-1, min, min+1, max-1, max, max+1).

White-box testing uses internal structure; statement coverage requires every executable statement to run at least once; branch coverage requires every decision outcome to be exercised.

Cyclomatic complexity V(G) = E − N + 2 for a connected control-flow graph, or P + 1 where P is the number of predicate (decision) nodes; it equals the minimum number of independent paths.

Unit tests isolate the smallest testable component; integration tests verify interactions between components; system tests validate end-to-end behavior against requirements.

Regression testing re-runs existing tests after a change to confirm that previously working functionality still works.

A test oracle is the mechanism that determines expected results; absence of a reliable oracle is a major challenge in automated test generation.

Mutation testing measures test-suite strength by injecting small code changes (mutants); a mutant is killed when at least one test fails on it, and the mutation score = killed / total mutants.