Software Engineering

4% of exam

Algorithms and complexity, data structures, iteration, recursion, control flow, testing.

3 concepts

Exam areas

A. Algorithms

Algorithms and Complexity

Read Big-O/Theta/Omega, compare searching and sorting costs, and solve recurrences so you can pick the right algorithm and predict how it scales.

Algorithm questions on the FE-ECE reward one skill above all: reading an algorithm and naming how its work grows with the input size

n

. You will not implement a sorter under time pressure — you will be handed pseudocode, a sorting-cost table, or a recurrence and asked which scales better as

n\to\infty

. The handbook hands you the asymptotic-cost table outright (Electrical and Computer Engineering: Algorithm Efficiency, Big-O), so the points go to whoever can interpret it: dropping constants, keeping the dominant term, and telling a

\log n

loop from an

n^2

nested loop at a glance. This concept builds that fluency from the definitions up so the table becomes obvious rather than memorized.

What Big-O actually claims

Big-O is an upper bound on growth:

f(n)=O(g(n))

means that for large enough

n

f

is bounded above by a constant multiple of

g

. The whole point is to ignore machine speed and small-

n

noise and keep only how cost scales. That is why

3n^2+50n+900

and

0.5n^2

are both

O(n^2)

— constants and lower-order terms vanish in the limit. The handbook makes this comparison rule explicit: compare two

O(\cdot)

values as

n

approaches infinity.

f(n)=O\bigl(g(n)\bigr)\iff \exists\,c>0,\,n_0:\ 0\le f(n)\le c\,g(n)\ \ \forall\,n\ge n_0

Theta and Omega: tight and lower bounds

Big-O alone only says 'no worse than.'

\Omega(g)

is the matching lower bound ('no better than'), and

\Theta(g)

means both hold at once — a tight description of growth. These two notations and the Master Theorem below are standard complexity tools, not entries in the FE handbook, but they sharpen how you read its average-vs-worst table. Merge sort is

\Theta(n\log n)

because it is both

O(n\log n)

and

\Omega(n\log n)

in every case; quicksort is

O(n^2)

in the worst case but

\Theta(n\log n)

on average. When a problem distinguishes 'average' from 'worst' (as the handbook table does), it is really asking you to separate these bounds.

\Theta(g)=O(g)\cap\Omega(g),\qquad f=\Theta(g)\iff c_1g(n)\le f(n)\le c_2 g(n)

The growth-rate hierarchy

Memorize the ladder, because every comparison question is a lookup against it. From cheapest to most expensive for large

n

: constant, logarithmic, linear, linearithmic, quadratic, cubic, then exponential and factorial. Logarithms beat any positive power of

n

for large

n

, so

n\log n

sits strictly between

n

and

n^2

. Anything

2^n

n!

is intractable past small

n

— recognizing one of these in pseudocode (e.g., a function that branches into two recursive calls with no memoization) is itself a common test point.

O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)

Time versus space

Complexity has two axes: time (operations executed) and space (extra memory beyond the input). They trade off. Iterative binary search runs in

O(\log n)

time and

O(1)

extra space; merge sort runs in

O(n\log n)

time but needs

O(n)

auxiliary space to merge, while heapsort matches its time at

O(1)

extra space. Recursion adds a hidden space cost: each pending call occupies a stack frame, so a recursion that descends to depth

d

uses

O(d)

space even when it returns a single number. Always ask which axis the question is grading.

\text{merge sort: } T=O(n\log n),\ S_{\text{aux}}=O(n)\quad\text{vs.}\quad \text{heap sort: } T=O(n\log n),\ S_{\text{aux}}=O(1)

Searching: linear versus binary

Linear search scans every element, so it is

O(n)

worst case and

O(n/2)\to O(n)

on average, but it works on unsorted data. Binary search requires a sorted array and halves the remaining range each step, so it finds (or rejects) any key in at most

\lceil\log_2 n\rceil

comparisons —

O(\log n)

. The exam loves the contrast: linear search needs no preprocessing; binary search needs sorted input but is exponentially faster. If the array is unsorted and you only search once, sorting first (

O(n\log n)

) is not worth it; if you search many times, it is.

\text{worst-case comparisons: }\ \text{linear}=n,\qquad \text{binary}=\lceil\log_2 n\rceil

Sorting complexities

Know the handbook table cold, because sorting is the single most-tested algorithm family. Bubble and insertion sort are simple but

O(n^2)

average and worst — fine for tiny or nearly-sorted lists, fatal at scale. Merge sort and heapsort are

\Theta(n\log n)

in every case (no bad inputs), which makes merge sort the safe answer when a problem demands a guaranteed bound. Quicksort averages

O(n\log n)

and is fast in practice but degrades to

O(n^2)

on a poor pivot (e.g., already-sorted input with a naive end pivot). Insertion sort's one virtue: it is

O(n)

on already-sorted data, the best case the others lack.

Recursion and recurrences

A recursive algorithm's cost is a recurrence: the work to solve size

n

in terms of the work on its subproblems. Binary search makes one recursive call on half the input, giving

T(n)=T(n/2)+O(1)

, which unwinds to

O(\log n)

. Merge sort makes two half-size calls plus an

O(n)

merge, giving

T(n)=2T(n/2)+O(n)\Rightarrow O(n\log n)

. The Master Theorem decides these by comparing the recombination cost

f(n)

n^{\log_b a}

: when they balance (merge sort), you pick up an extra

\log n

factor. Naive recursive Fibonacci,

T(n)=T(n-1)+T(n-2)+O(1)

, branches without overlap-sharing and explodes to

O(\varphi^n)

— the textbook case for memoization or iteration.

T(n)=a\,T\!\left(\tfrac{n}{b}\right)+f(n),\quad\text{compare } f(n)\text{ to } n^{\log_b a}\ \Rightarrow\ \text{Master Theorem}

Iteration versus recursion in cost

An iterative loop and an equivalent tail recursion do the same asymptotic time, but recursion carries the stack-space penalty above and a constant-factor call overhead. The deeper lesson the exam tests is that restructuring an algorithm changes its class, not just its constant: turning the doubly-recursive Fibonacci into a single loop drops it from exponential to

O(n)

time and

O(1)

space. So when you see two ways to compute the same result, classify each by its recurrence — the cheaper class wins regardless of language or hardware.

\text{iterative Fibonacci: } O(n)\text{ time},\ O(1)\text{ space}\quad\text{vs.}\quad\text{naive recursive: } O(\varphi^{\,n})

Exam strategy

Triage every algorithm question to one of four moves: (1) given pseudocode, count the deepest loop nesting —

k

independent nested loops over

n

O(n^k)

, a halving loop is

O(\log n)

; (2) given the handbook table, read off average vs. worst for the named sort or structure; (3) given a recurrence, match it to binary-search (

O(\log n)

), merge-sort (

O(n\log n)

), or exponential branching; (4) to compare two algorithms, drop constants and lower-order terms, then place each on the

O(1)<\log n<n<n\log n<n^2

ladder. Watch the qualifier 'average' vs. 'worst' — quicksort and hash tables answer differently for each.

Key equations

Big-O (upper bound)

f(n)=O(g(n))\iff \exists\,c,n_0:\ f(n)\le c\,g(n)\ \forall n\ge n_0

Asymptotic ceiling on growth; drop constants and lower-order terms. Used to state worst-case scaling of an algorithm.

Big-Omega (lower bound)

f(n)=\Omega(g(n))\iff \exists\,c,n_0:\ f(n)\ge c\,g(n)\ \forall n\ge n_0

Asymptotic floor on growth; states the best the algorithm can do for large $n$ .

Big-Theta (tight bound)

f(n)=\Theta(g(n))\iff f=O(g)\ \text{and}\ f=\Omega(g)

Exact growth class. Merge/heap sort are $\Theta(n\log n)$ in all cases; use when both bounds match.

Growth hierarchy

O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)

Ordering for large $n$ . Resolve any 'which is faster' question by placing each candidate on this ladder.

Binary search cost

T(n)=T(n/2)+O(1)\Rightarrow O(\log_2 n)

Comparisons to find/reject a key in a SORTED array of $n$ elements; at most $\lceil\log_2 n\rceil$ .

Linear search cost

T_{\text{worst}}=n,\qquad T_{\text{avg}}=\tfrac{n}{2}\ \to\ O(n)

Scan of an unsorted array of $n$ elements; no preprocessing required.

Merge / heap sort

T(n)=2T(n/2)+O(n)\Rightarrow \Theta(n\log n)

Guaranteed linearithmic in every case. Merge sort needs $O(n)$ aux space; heap sort needs $O(1)$ .

Quick sort

T_{\text{avg}}=O(n\log n),\quad T_{\text{worst}}=O(n^2)

Fast average pivot-partition sort; degrades to $O(n^2)$ on a poor pivot (e.g., sorted input, naive pivot).

Bubble / insertion sort

T_{\text{avg}}=T_{\text{worst}}=O(n^2),\quad T_{\text{best,insertion}}=O(n)

Simple $O(n^2)$ sorts; insertion sort is $O(n)$ on already-sorted data, the others' best case is still $O(n^2)$ .

Master Theorem form

T(n)=a\,T(n/b)+f(n)

Solve divide-and-conquer recurrences by comparing $f(n)$ with $n^{\log_b a}$ ; equal magnitude adds a $\log n$ factor.

Naive recursive Fibonacci

T(n)=T(n-1)+T(n-2)+O(1)=\Theta(\varphi^{\,n})

Branching recursion without memoization is exponential; the iterative version is $O(n)$ time, $O(1)$ space.

Polynomial-time runtime scaling

\frac{T(kn)}{T(n)}=k^{\,p}\quad\text{for } T(n)=\Theta(n^p)

How runtime scales when input multiplies by $k$ . For $O(n^2)$ , doubling input quadruples time.

Worked examples

Binary vs. linear search comparisons

Problem. A sorted array holds $n=1{,}000{,}000$ records. Give the worst-case number of comparisons for (a) linear search and (b) binary search, and state each cost in Big-O.

Solution. Linear search examines every element in the worst case:

n=1{,}000{,}000

comparisons, which is

O(n)

. Binary search halves the range each step, so the worst case is

\lceil\log_2 n\rceil

. Here

\log_2(10^6)=19.93

, so

\lceil 19.93\rceil = 20

comparisons, which is

O(\log n)

. Sanity check:

2^{20}=1{,}048{,}576 \ge 10^6

, so 20 halvings cover the whole array; binary search is about

50{,}000\times

fewer comparisons here. Final: linear

=1{,}000{,}000

(

O(n)

); binary

=20

(

O(\log n)

\lceil\log_2(10^6)\rceil=\lceil 19.93\rceil = 20\ \text{comparisons}

Runtime scaling of an O(n²) algorithm

Problem. An algorithm whose running time is $\Theta(n^2)$ takes $3.0\,\text{s}$ to process $n=10{,}000$ items. Estimate the time to process $40{,}000$ items. How would an $O(n\log n)$ algorithm scale over the same change?

Solution. The input multiplies by

k=40{,}000/10{,}000=4

. For

\Theta(n^2)

, time scales by

k^2=4^2=16

, so

t = 3.0\times 16 = 48.0\,\text{s}

. For

O(n\log n)

: ratio

=\dfrac{40{,}000\log_2 40{,}000}{10{,}000\log_2 10{,}000}=\dfrac{40{,}000(15.29)}{10{,}000(13.29)}=4.60

, so

t = 3.0\times 4.60 = 13.8\,\text{s}

. Sanity check: linearithmic grows just above linear (4×) and far below quadratic (16×), as expected. Final:

48.0\,\text{s}

quadratic vs.

13.8\,\text{s}

linearithmic.

t_{n^2}=3.0\,(4^2)=48.0\,\text{s},\qquad t_{n\log n}=3.0\times 4.60 = 13.8\,\text{s}

Classifying a recurrence

Problem. An algorithm satisfies $T(n)=2T(n/2)+cn$ for constant $c$ . Give its Big-O time, name an algorithm with this recurrence, and contrast it with $T(n)=T(n-1)+T(n-2)+c$ .

Solution. Master Theorem:

a=2

b=2

, so

n^{\log_b a}=n^{\log_2 2}=n^1=n

. The recombination cost

f(n)=cn

matches

n^1

, the balanced case, which adds a

\log n

factor:

T(n)=\Theta(n\log n)

. This is merge sort (split in two,

O(n)

merge). The second recurrence branches into two nearly full-size calls and shares no work, giving

T(n)=\Theta(\varphi^{\,n})\approx O(1.618^n)

— exponential. This is naive recursive Fibonacci. Sanity check: at

n=8

, the merge-sort work

n\log_2 n = 8(3)=24

operations, while naive Fibonacci makes

2\,F(9)-1=67

recursive calls to compute

F(8)

— already roughly

3\times

larger, and the gap explodes past that. Final: merge-sort recurrence is

O(n\log n)

; the Fibonacci recurrence is exponential.

n^{\log_2 2}=n=f(n)\Rightarrow T(n)=\Theta(n\log n)

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)$ worst. Read which the question wants.
•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)$ (keep the larger).
•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.

B. Data structures

Data Structures

Match arrays, lists, stacks, queues, trees, hash tables, and graphs to their operation costs so you can pick the structure that makes the required operations cheap.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders

C. Software implementation

Software Implementation

Trace pseudocode control flow, convert between recursion and iteration, reason about data types and overflow, and place testing and SDLC concepts the FE expects.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders