2.10 Analyzing the time complexity of recursive algorithms

Recurrence relations

The runtime complexity T(N) of a recursive function will have function T on both sides of the equation. Ex: Binary search performs constant time operations, then a recursive call that operates on half of the input, making the runtime complexity T(N) = O(1) + T(N / 2). Such a function is known as a recurrence relation: A function f(N) that is defined in terms of the same function operating on a value < N.

Using O-notation to express runtime complexity of a recursive function requires solving the recurrence relation. For simpler recursive functions such as binary search, runtime complexity can be determined by expressing the number of function calls as a function of N.

Activity 1: Binary search and recurrence relations.

  1. When the low and high arguments are equal, BinarySearch does not make a recursive call.
    True
    False


  2. Suppose BinarySearch is used to search for a key within a list with 64 numbers. If the key is not found, how many recursive calls to BinarySearch are made?
    1
    6
    64


  3. Which function is a recurrence relation?
    T(N) = N² + 6N + 2
    T(N) = 6N + T(N4)
    T(N) = log N


Recursion trees

The runtime complexity of any recursive function can be split into 2 parts: operations done directly by the function and operations done by recursive calls made by the function. Ex: For binary search's T(N) = O(1) + T(N / 2), O(1) represents operations directly done by the function and T(N / 2) represents operations done by a recursive call. A useful tool for solving recurrences is a recursion tree: A visual diagram of a operations done by a recursive function, that separates operations done directly by the function and operations done by recursive calls.

Activity 2: Matching recursion trees with runtime complexities.

  1. T(N) = k + T(N2) + T(N2)
    Tree 1
    Tree 2
    Tree 3
    Tree 4


  2. T(N) = k + T(N - 1)
    Tree 1
    Tree 2
    Tree 3
    Tree 4


  3. T(N) = N + T(N - 1)
    Tree 1
    Tree 2
    Tree 3
    Tree 4


  4. T(N) = N + T(N2) + T(N2)
    Tree 1
    Tree 2
    Tree 3
    Tree 4


Activity 3: Recursion trees.

Suppose a recursive function's runtime is T(N) = 7 + T(N āˆ’ 1).

  1. How many levels will the recursion tree have?
    7
    log N
    N


  2. What is the runtime complexity of the function using O notation?
    O(1)
    Olog(N)
    O(N)


Suppose a recursive function's runtime is T(N) = N + T(N āˆ’ 1).

  1. How many levels will the recursion tree have?
    log N
    N


  2. The runtime can be expressed by the series N + (N - 1) + (N - 2) + ... + 3 + 2 + 1. Which expression is mathematically equivalent?
    N * log N
    (N2) * (N + 1)


  3. What is the runtime complexity of the function using O notation?
    O(N)
    O(N²)