Software Engineering

What Big-O actually claims

Theta and Omega: tight and lower bounds

The growth-rate hierarchy

Time versus space

Searching: linear versus binary

Sorting complexities

Recursion and recurrences

Iteration versus recursion in cost

Exam strategy

Key equations

Worked examples

Common pitfalls

• •Keeping constants or lower-order terms: $4n^2+100n$ is $O(n^2)$, not $O(4n^2+100n)$ — Big-O discards both the coefficient and the linear term.
• •Confusing average and worst case: quicksort is $O(n\log n)$ average but $O(n^2)$ worst; a hash lookup is $O(1)$ average but $O(n)$
• •Calling binary search on unsorted data: it requires a sorted array. On unsorted data only linear search ($O(n)$) is valid unless you first sort ($O(n\log n)$).
• •Adding instead of multiplying nested-loop bounds: two nested loops each over $n$ are $O(n^2)$ (multiply); two sequential loops are $O(n)+O(n)=O(n)$
• •Forgetting recursion's space cost: a recursion descending to depth $d$ uses $O(d)$ stack space even if it returns one value — relevant when a problem grades memory.
• •Treating $n\log n$ as if it equals $n^2$ or $n$: it sits strictly between them. Dismissing the $\log n$ factor flips comparison answers.
• •Assuming recursion is automatically slower or faster than iteration: same asymptotic time, but recursion adds stack space and call overhead; restructuring (e.g., Fibonacci) can change the actual complexity class.

References

• NCEES FE Reference Handbook — Electrical and Computer Engineering: Algorithms and Algorithm Efficiency (Big-O) — Source of the average/worst-case cost table for the named sorts and structures.
• NCEES FE Reference Handbook — Electrical and Computer Engineering: Software Syntax Guidelines — Defines the pseudocode conventions used to present algorithm questions on the exam.
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms — Asymptotic notation, the Master Theorem, and sorting/searching analyses.