To describe efficiency, look at how an algorithm's work and memory requirements grow as the input gets larger. Calculate the growth rate first. Then judge whether the algorithm will scale to the required workload.

Time, space and input size

Time complexity describes how the amount of work an algorithm performs grows with input size. Count relevant operations, such as comparisons, rather than timing it in seconds on one particular computer.

Space complexity describes how memory requirements grow with input size. Make clear whether your calculation includes the input itself or just the additional memory the algorithm uses.

Let n represent the input size—for example, the number of elements being searched or sorted. Auxiliary space is the extra memory an algorithm requires, excluding storage for the input.

Searching an existing array with only an index and a few other variables uses O(1) auxiliary space. But the array itself occupies O(n) space, so the total storage requirement is not constant.

Calculating Big O notation

Big O notation expresses an asymptotic upper bound on growth as input size increases. In these notes, use it to describe the dominant growth rate for a stated case, such as the worst case.

To calculate it:

1. Identify the input size and the operation being counted.
2. Work out how often that operation can occur.
3. Keep the fastest-growing term and discard constant multipliers.

Suppose, for example, an algorithm performs 3n² + 5n + 2 operations. Eventually, the n² term dominates the linear and constant terms. Remove its constant multiplier to get O(n²).

For two separate scans, add the costs: n + n gives 2n. The result is O(n), not O(n²). Multiply when one complete repetition is nested inside another.

Halve a region of size 8 and the sizes become 4, 2 and 1—only three reductions. In Big O notation, the logarithm's base is normally omitted because changing the base changes only a constant multiplier.

Comparing growth rates

Doubling n roughly doubles linear work but quadruples quadratic work. Logarithmic work grows much more slowly: each step removes a large fraction of the remaining problem.

Choosing an algorithm

Scalability is an algorithm's ability to remain practical as the input or workload grows. To be suitable, an algorithm must meet both time and memory requirements.

Use the same assumptions when comparing algorithms:

• Best case: the input causes the least work, such as finding a search target immediately.
• Worst case: the input causes the most work, such as checking every element without finding a target.
• Average case: the expected work under stated assumptions about the inputs.

Big O doesn't give an exact execution time. With a small input, setup costs and constant factors can matter more than the growth rate. With a large input, a lower growth rate can make the difference between a practical and an impractical solution.

Preparation matters too. If a faster search requires sorted data, preparing that data may not be worth it for a single lookup. It may be worthwhile when many lookups reuse the same sorted data. An algorithm can also meet a time target yet remain unsuitable if its additional memory exceeds the available space.

Terms to use: time complexity, space complexity, Big O notation, scalability, efficiency.

Construct each search by deciding which element to examine next, when to stop and what to return. Trace it by recording the indices examined and the changes to the remaining search region.

Linear search

Linear search examines elements in sequence until it finds the target or reaches the end of the collection. It does not require the data to be sorted.

The implementations below return the index of the first matching element. They return -1 if no match exists. Both search the readings 6, 10, 14, 18, 22, 26 and 30 for the target 22.

Java

1  public class LinearSearchDemo {
2      public static int linearSearch(int[] readings, int target) {
3          for (int index = 0; index < readings.length; index++) {
4              if (readings[index] == target) {
5                  return index;
6              }
7          }
8          return -1;
9      }
10     public static void main(String[] args) {
11         int[] readings = {6, 10, 14, 18, 22, 26, 30};
12         int target = 22;
13         System.out.println(linearSearch(readings, target));
14     }
15 }

Python

1  def linear_search(readings, target):
2      for index in range(len(readings)):
3          if readings[index] == target:
4              return index
5      return -1
6  readings = [6, 10, 14, 18, 22, 26, 30]
7  target = 22
8  print(linear_search(readings, target))

The trace records each comparison. The readings and target remain unchanged throughout the run.

There are five comparisons. Finding the first element takes O(1) time; an unsuccessful search or a match at the final element takes O(n) time. Average time is O(n) when successful targets are equally likely to occupy any position. Auxiliary space is O(1).

On ascending sorted data, a modified linear search can also stop when the current value exceeds the target. This avoids unnecessary later comparisons, but its worst-case time remains O(n).

Binary search

Binary search repeatedly compares a target with the middle element of a sorted search region and discards the half that cannot contain it. The data must be sorted by the field being searched.

Use three indices: low is the first possible position, high is the last possible position and middle is the position being tested. If the middle value is below the target, move low just beyond middle. If it is above the target, move high just before middle.

Java

1  public class BinarySearchDemo {
2      public static int binarySearch(int[] readings, int target) {
3          int low = 0;
4          int high = readings.length - 1;
5          while (low <= high) {
6              int middle = low + (high - low) / 2;
7              if (readings[middle] == target) {
8                  return middle;
9              }
10             if (readings[middle] < target) {
11                 low = middle + 1;
12             } else {
13                 high = middle - 1;
14             }
15         }
16         return -1;
17     }
18     public static void main(String[] args) {
19         int[] readings = {6, 10, 14, 18, 22, 26, 30};
20         int target = 22;
21         System.out.println(binarySearch(readings, target));
22     }
23 }

Python

1  def binary_search(readings, target):
2      low = 0
3      high = len(readings) - 1
4      while low <= high:
5          middle = low + (high - low) // 2
6          if readings[middle] == target:
7              return middle
8          if readings[middle] < target:
9              low = middle + 1
10         else:
11             high = middle - 1
12     return -1
13 readings = [6, 10, 14, 18, 22, 26, 30]
14 target = 22
15 print(binary_search(readings, target))

The trace separates a comparison from any resulting boundary change. middle is recalculated at the start of each repetition.

An unsuccessful search eventually makes low greater than high, meaning no candidate positions remain. Moving a boundary beyond middle, rather than leaving it at middle, ensures that an unsuccessful search continues to make progress.

Binary search has O(1) best-case time and O(log n) average and worst-case time on a sorted array. The iterative implementations above use O(1) auxiliary space. With duplicate values, they return a matching index, not necessarily the first matching index.

Choosing between the searches

Suppose a repair centre stores equipment records in ascending asset-code order. Binary search can retrieve a record by asset code. Searching for an owner's email address cannot use that order to discard half the records: use linear search unless a separate ordering or suitable index for email addresses exists.

Sorting is therefore a property of a particular search key, not a guarantee that binary search works for every field in a record.

Terms to use: linear search, binary search, data retrieval, efficiency.

Construct both sorts by identifying what becomes correctly positioned after each pass. Trace their comparisons and changes to the array, then evaluate the time and auxiliary space they require for different input arrangements.

Bubble sort

Bubble sort repeatedly compares adjacent elements and swaps them when they are in the wrong order. In an ascending sort, a complete left-to-right pass moves the largest remaining value to the end of the unsorted region.

Each pass can finish one position earlier because the previous pass placed an element in its final position. The version below also records whether any swap occurred: a pass with no swaps proves that the whole array is already sorted.

Both language versions sort 8, 3, 6 and 2 in place, meaning that they modify the original array or list rather than build a separate sorted copy.

Java

1  import java.util.Arrays;
2  public class BubbleSortDemo {
3      public static void bubbleSort(int[] values) {
4          for (int end = values.length - 1; end > 0; end--) {
5              boolean swapped = false;
6              for (int index = 0; index < end; index++) {
7                  if (values[index] > values[index + 1]) {
8                      int temporary = values[index];
9                      values[index] = values[index + 1];
10                     values[index + 1] = temporary;
11                     swapped = true;
12                 }
13             }
14             if (!swapped) {
15                 break;
16             }
17         }
18     }
19     public static void main(String[] args) {
20         int[] values = {8, 3, 6, 2};
21         bubbleSort(values);
22         System.out.println(Arrays.toString(values));
23     }
24 }

Python

1  def bubble_sort(values):
2      for end in range(len(values) - 1, 0, -1):
3          swapped = False
4          for index in range(end):
5              if values[index] > values[index + 1]:
6                  values[index], values[index + 1] = values[index + 1], values[index]
7                  swapped = True
8          if not swapped:
9              break
10 values = [8, 3, 6, 2]
11 bubble_sort(values)
12 print(values)

The trace uses a checkpoint after each comparison and any completed swap. temporary is a short-lived Java variable used only during a swap; Python performs the exchange using simultaneous assignment.

This run performs six comparisons and five swaps. The completed passes fix 8, then 6, then 3 in their final positions.

Selection sort

Selection sort repeatedly finds the smallest element in the unsorted region and exchanges it with the first element of that region. After each pass, the sorted region at the beginning grows by one element.

Keep the index of the smallest value found so far, not just its value: the index identifies which element to exchange. The implementations avoid a swap when the smallest element is already at the start of the unsorted region.

Java

1  import java.util.Arrays;
2  public class SelectionSortDemo {
3      public static void selectionSort(int[] values) {
4          for (int start = 0; start < values.length - 1; start++) {
5              int smallest = start;
6              for (int scan = start + 1; scan < values.length; scan++) {
7                  if (values[scan] < values[smallest]) {
8                      smallest = scan;
9                  }
10             }
11             if (smallest != start) {
12                 int temporary = values[start];
13                 values[start] = values[smallest];
14                 values[smallest] = temporary;
15             }
16         }
17     }
18     public static void main(String[] args) {
19         int[] values = {8, 3, 6, 2};
20         selectionSort(values);
21         System.out.println(Arrays.toString(values));
22     }
23 }

Python

1  def selection_sort(values):
2      for start in range(len(values) - 1):
3          smallest = start
4          for scan in range(start + 1, len(values)):
5              if values[scan] < values[smallest]:
6                  smallest = scan
7          if smallest != start:
8              values[start], values[smallest] = values[smallest], values[start]
9  values = [8, 3, 6, 2]
10 selection_sort(values)
11 print(values)

The trace records each comparison, followed by the exchange at the end of a pass when one is needed.

Selection sort performs six comparisons but only one swap on this input. Although the first pass happens to put the whole array in order, the algorithm still scans the remaining regions.

Calculating their complexities

Without early termination, the comparison counts are:

(n − 1) + (n − 2) + ... + 1 = n(n − 1) / 2.

Expanding gives (n² − n) / 2. The dominant term is quadratic, so the time complexity is O(n²).

Both sorts need only a fixed number of indices, flags or temporary values, so their auxiliary space is constant. Including the input array itself gives O(n) total storage.

Evaluating the choice

Bubble sort is useful when a small collection may already be sorted: the no-swap check can finish after one scan. It can also benefit from some nearly sorted arrangements, but a value that must move a long way towards the beginning may require many passes. Nearly sorted does not automatically mean linear time.

Reverse-ordered data causes many adjacent exchanges in bubble sort. Selection sort still makes its usual quadratic number of comparisons, but limits the number of exchanges. This is an advantage when moving records is expensive compared with comparing them.

For large data sets, both algorithms' quadratic growth is a major limitation. Their small auxiliary-space requirement does not remove that time cost. Also, bubble sort without the no-swap check would have O(n²) best-case time: the implementation matters.

Terms to use: bubble sort, selection sort, time complexity, space complexity, Big O notation, efficiency.

To explain recursion, show how a function reduces a problem, where it stops calling itself and how the results return through earlier calls. Recursion is useful when it matches the problem's structure. Each unfinished call, though, has a memory cost.

How recursion works

Recursion is a technique in which a function calls itself to solve a smaller instance of a problem.

A correct recursive solution needs three features:

• A base case that can be solved without another recursive call.
• A recursive case that reduces the problem and makes a recursive call.
• Progress towards the base case so that the chain of calls terminates.

Take the sum of the integers from 1 to 3. It can be written as 3 plus the sum up to 2. The smaller sum is 2 plus the sum up to 1; reducing it again reaches the sum up to 0, which is 0. Each call uses a smaller non-negative input.

The call stack stores information about active function calls. Every recursive call has its own parameter values and local variables. Earlier calls wait for the results they need.

The base case doesn't necessarily finish the whole calculation. Earlier calls may still need to do some work with the returned value.

Why smaller, similar problems are useful

Recursion suits problems whose parts have the same structure as the whole. One function can process the current level and delegate the smaller instances, rather than describe every level separately.

In these applications, a single call may make more than one recursive call. That branching structure helps explain recursion, although a simple recursive calculation may make just one further call at each stage.

Quicksort

Quicksort partitions data around a chosen pivot, then recursively sorts the smaller regions it creates. The pivot separates values that belong before it from those that belong after it in the final order.

A conceptual ascending quicksort works as follows:

1. Stop if the region contains zero or one element.
2. Choose a pivot, a value used to divide the region.
3. Partition the other values into those below the pivot and those above it, handling equal values consistently.
4. Recursively sort the smaller regions.
5. The sorted lower region, pivot and sorted upper region form the sorted result.

This is the logical partitioning. An implementation can rearrange values within the original array instead of allocating a new list for every region.

Quicksort efficiency

Reasonably balanced partitions give O(log n) levels of recursive work. Partitioning examines O(n) elements in total across each level, giving average time O(n log n).

A much deeper chain develops if each pivot leaves one empty region and another of size n − 1. The work accumulates as n + (n − 1) + ... + 1, giving O(n²) worst-case time. Choosing an end value as pivot on already sorted, distinct data, for example, can produce this behaviour.

With in-place partitioning that recursively processes both regions, the call stack typically needs O(log n) auxiliary space for balanced partitions. In the worst case, it can need O(n). Creating separate lists adds memory costs beyond the call stack.

Advantages and limitations

Recursion can closely match a fractal, tree or partitioning problem. This can make the structure clearer than manually managing every unfinished sub-problem. The same solution can also work at different depths without separate instructions for each depth.

That doesn't make recursion automatically efficient. Its time complexity depends on the number of calls and the work each call performs. Memory use depends on the maximum number of calls active at once, plus any additional data they allocate.

Every call adds overhead: its state must be stored, and it must return to its caller. Excessive depth can exhaust the available call-stack memory. A missing base case, or a recursive step that fails to move towards it, can therefore cause failure instead of producing a useful result.

For a straightforward repeated calculation, a loop is often simpler. Recursion is especially suitable for naturally nested or self-similar problems, provided its depth and resource use remain practical.

Terms to use: recursion, recursive algorithms, quicksort, complexity, memory usage, fractal image creation, traversing binary trees, sorting algorithms.

Construct a simple recursive function by writing its stopping rule before its recursive step. Trace both the calls made on the way down and the values returned on the way back up.

Constructing a non-branching recursive solution

A non-branching recursive algorithm makes at most one recursive call from each invocation. Its active calls form a single chain rather than a branching tree.

The worked function returns the sum of the integers from 1 to a non-negative integer n. For an input of 0, it returns 0.

Build the solution in this order:

1. Define the input restriction: n must be a non-negative integer.
2. Identify the base case: the sum up to 0 is 0.
3. Reduce the problem: the sum up to n is n plus the sum up to n − 1.
4. Return the smaller problem's result combined with n.

Subtracting one moves every valid positive input towards the base case. Negative inputs are outside this function's stated input domain: subtracting one from them would move away from 0.

Java

1  public class RecursiveSumDemo {
2      public static int sumTo(int n) {
3          if (n == 0) {
4              return 0;
5          }
6          return n + sumTo(n - 1);
7      }
8      public static void main(String[] args) {
9          int result = sumTo(3);
10         System.out.println(result);
11     }
12 }

Python

1  def sum_to(n):
2      if n == 0:
3          return 0
4      return n + sum_to(n - 1)
5  result = sum_to(3)
6  print(result)

In Java, line 6 waits for the smaller call's result before completing the addition. Python line 4 does the same. Neither line simply restarts the original call: each invocation has its own value of n.

Tracing calls and returns

The trace follows the execution for input 3. Each row identifies the current call's local n; the caller's value remains stored in its own stack frame while it waits.

Checking termination and resource use

The base case returns directly, without another call. Every recursive call reduces n by one. Together, these properties ensure termination for the stated input domain.

For input n, the function makes n + 1 calls, including the base case. Each call performs constant additional work, so the time complexity is O(n).

The maximum call-stack depth is also n + 1. Each waiting call stores a fixed amount of state, so auxiliary space is O(n). Having only a few local variables in each call does not make the whole recursive algorithm's memory use constant.

A loop could calculate the same sum with O(1) auxiliary space. The recursive version makes the reduction and return process explicit, but it still carries the memory cost of its waiting calls.

Terms to use: recursive algorithms, programming language, non-branching recursive algorithms.