FE Electrical Software Engineering Practice Problems

Answer: C) \(O(n)\)

A linear search compares the target with one element after another, in order, until it finds a match or runs off the end. Nothing about an unsorted array lets it skip anything: in the worst case the target is the last element, or is absent altogether, and every one of the \(n\) elements has been examined.

$$T(n) = n \text{ comparisons} = O(n)$$

Big O describes how the work grows with \(n\), and here it grows in direct proportion: double the array, double the worst-case work. Linear search is not in the Handbook's efficiency table, but it is the baseline every entry in that table is measured against.

\(O(\log n)\) is binary search, which halves the remaining range at each comparison. It needs the array to be sorted; on an unsorted array there is no way to know which half to discard.

\(O(1)\) is constant time, the cost of a hash-table lookup or of reading one array element by index. A search that must look at the data cannot run in time independent of how much data there is.

\(O(n \log n)\) is the cost of a good sort, not of a search. Sorting first and then binary-searching would cost more than one linear pass, not less.

Answer: A) \(O(1)\)

The Handbook defines an array as a collection whose elements are accessed by an integer index, and that definition hides the reason for the answer. An array's elements sit in consecutive memory locations, so the location of element \(i\) is a single arithmetic expression:

$$\text{address of element } i = \text{start of array} + (i - 1) \times \text{size of one element}$$

One multiplication and one addition, whatever the value of \(i\) and whatever the size of the array. That is constant time, \(O(1)\), and it is the single property that makes arrays the right structure whenever data is read by position - it is also what binary search relies on to jump to the middle.

\(O(i)\) is the cost of reaching position \(i\) in a linked list, whose nodes can only be found by following pointers from the head one node at a time. It is the natural wrong answer for anyone picturing the wrong structure.

\(O(n)\) is the cost of searching an unsorted array for a value. Reading by index and searching by value are different operations; only the second has to look at the data.

\(O(\log n)\) is binary search, again a search by value and one that needs sorted data.

Answer: C) 120

A recursive function is read by unwinding it. Each call with \(n > 1\) multiplies \(n\) by the result of the call for \(n - 1\), and the chain stops at the base case \(n \le 1\), which returns 1 without calling anything:

$$\text{factorial}(5) = 5 \cdot \text{factorial}(4) = 5 \cdot 4 \cdot \text{factorial}(3) = 5 \cdot 4 \cdot 3 \cdot 2 \cdot \text{factorial}(1) = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$$

The base case is what makes the recursion finish: without it the calls would descend through 0, \(-1\), \(-2\) and never return. The Handbook does not describe recursion, so the discipline of checking for the base case first is one to bring to the exam.

24 is \(4!\), the result of stopping one level early - reading the base case as \(n \le 2\), or forgetting the outermost factor of 5.

720 is \(6!\), one level too many.

60 is \(5 \cdot 4 \cdot 3\), the chain abandoned before reaching the base case.

Answer: B) 4

Quadratic time means the running time is proportional to the square of the input size. Doubling the input squares the doubling:

$$\dfrac{T(2n)}{T(n)} = \dfrac{c(2n)^2}{cn^2} = \dfrac{4cn^2}{cn^2} = 4$$

The constant \(c\) cancels, and so does \(n\): for any polynomial the ratio is the same whatever the starting size, which is exactly why Big O is useful. It tells you how an algorithm scales without knowing how fast the machine is. The rule generalises: an \(O(n^k)\) algorithm slows by \(2^k\) when the input doubles, so the exponent is the whole story.

2 is the linear answer, \(O(n)\): doubling the input doubles the work. A quadratic algorithm does worse than that because every element interacts with every other.

8 is \(2^3\), the factor for a cubic algorithm.

16 is \(2^4\), or equivalently the factor of 4 squared a second time - the doubling applied to the exponent as well as to the input.

Answer: C) \(O(n \log n)\)

Count the inner statement's executions. The outer loop runs \(n\) times. Inside it, \(j\) starts at 1 and doubles on every pass, so it takes the values \(1, 2, 4, \ldots, 2^k\) and the loop continues while \(2^k \le n\) - that is, \(\lfloor \log_2 n \rfloor + 1\) passes. The inner count does not depend on \(i\), so the total is simply the product:

$$n \times (\lfloor \log_2 n \rfloor + 1) = O(n \log n)$$

The rule to carry away: a loop whose variable is multiplied by a constant each time runs a logarithmic number of times, while one whose variable is incremented runs a linear number of times. Nested loops multiply their counts.

\(O(n^2)\) treats the inner loop as linear, as it would be if \(j\) advanced by \(j = j + 1\). The doubling is what changes everything.

\(O(n)\) counts only the outer loop, as though the inner one ran a constant number of times. It runs \(\log_2 n\) times, and that grows.

\(O(\log^2 n)\) makes both loops logarithmic. The outer variable is incremented, not doubled, so it is linear.