FE Electrical and Computer Software Engineering Practice Problems

The current FE Electrical and Computer specification assigns 4-6 of the 110 exam questions to Software Engineering. Form A contains 4 original problems in this area. The sample below is published in full, with the same worked-solution format used throughout the book.

A batch record-sorting routine in a utility billing system uses a comparison sort whose running time grows as $n lo g_{2} n$ , where $n$ is the number of records. Sorting 100{,}000 records requires 0.42 s on the target processor. On the same processor, the time required to sort 800{,}000 records is most nearly:

(A)3.36 s
(B)3.97 s
(C)26.9 s
(D)31.7 s

Show worked solution

Answer: (B)

An eightfold increase in record count costs a factor of 9.44 in time, since the logarithmic factor grows too, and the sort runs about 3.97 s.

Runtime for a comparison sort is proportional to $n lo g_{2} n$ , so the unknown machine constant cancels when two problem sizes are compared as a ratio.

\frac{T _{2}}{T _{1}} = \frac{n _{2} lo g _{2} n _{2}}{n _{1} lo g _{2} n _{1}}

The record count rises by a factor of eight while the logarithmic factor rises only from $lo g_{2} (100, 000) = 16.610$ to $lo g_{2} (800, 000) = 19.610$ .

\frac{T _{2}}{T _{1}} = 8 \times \frac{19.610}{16.610} = 9.445

Scaling the measured 0.42 s by that factor gives the projected batch time.

T_{2} = 0.42 s \times 9.445 = 3.97 s

FE Reference Handbook — Software Engineering: Algorithms, Algorithm Efficiency (Big-O Notation)

Why the other choices appear

(A)Treats the growth as purely linear in $n$ , giving $0.42 \times 8 = 3.36$ s and discarding the logarithmic factor.
(C)Assumes quadratic growth $n^{2}$ , giving $0.42 \times 8^{2} = 26.9$ s.
(D)Combines quadratic and logarithmic growth as $n^{2} lo g_{2} n$ , giving $0.42 \times 64 \times 1.1806 = 31.7$ s.