How to analyze the time and space complexity of a recursion function?

We can answer that using master theorem or induction in most of the cases.

First of all, we need to write down the recursion relation of a function.

Let’s use T(n) to denote the running time of func with input size of n.

Then we have：

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

a = 2, b = 2, c_crit = logb(a) = 1, f(n) = n^c, c = 0.

c < c_crit, apply master theorem case 1:

T(n) =  Θ(n^c_crit) = Θ(n)

Let’s look at another example:

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

a = 2, b = 2, c_crit = logb(a) = 1, f(n) = n^c, c = 1,

c = c_crit, apply master theorem case 2:

T(n) =Θ(n^c_crit * (logn)^1)) = Θ(nlogn)

Cheatsheet

Equation Time Space Examples
T(n) = 2*T(n/2) + O(n) O(nlogn) O(logn) quick_sort
T(n) = 2*T(n/2) + O(n) O(nlogn) O(n + logn) merge_sort
T(n) = T(n/2) + O(1) O(logn) O(logn) Binary search
T(n) = 2*T(n/2) + O(1) O(n) O(logn) Binary tree traversal
T(n) = T(n-1) + O(1) O(n) O(n) Binary tree traversal
T(n) = T(n-1) + O(n) O(n^2) O(n) quick_sort(worst case)
T(n) = n * T(n-1) O(n!) O(n) permutation
T(n) = T(n-1)+T(n-2)+…+T(1) O(2^n) O(n) combination

For recursion with memorization:

Time complexity: |# of subproblems| * |exclusive running time of a subproblem|

Space complexity:|# of subproblems|  + |max recursion depth| * |space complexity of a subproblem|

Example 1:

To solve fib(n), there are n subproblems fib(0), fib(1), …, fib(n)

each sub problem takes O(1) to solve

Time complexity: O(n)

Space complexity: O(n) + O(n) * O(1) = O(n)

Example 2:

LC 741 Cherry Pickup

To solve dp(n, n, n), there are n^3 subproblems

each subproblem takes O(1) to solve

Max recursion depth O(n)

Time complexity: O(n^3) * O(1) = O(n^3)

Space complexity: O(n^3) + O(n) * O(1) = O(n^3)

Example 3:

LC 312: Burst Balloon

To solve dp(0, n), there are n^2 subproblems dp(0, 0), dp(0, 1), …, dp(n-1, n)

each subproblem takes O(n) to solve

Max recursion depth O(n)

Time complexity: O(n^2) * O(n) = O(n^3)

Space complexity: O(n^2) + O(n) * O(1) = O(n^2)

Slides:

Problem:

On a 2×3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

Solution: BFS

Time complexity: O(6!)

Space complexity: O(6!)

C++

Simplified, only works on 3×2 board

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Note:

1. Input logs will be sorted by timestamp, NOT log id.
2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
3. Two functions won’t start or end at the same time.
4. Functions could be called recursively, and will always end.
5. 1 <= n <= 100

Solution: Simulate using stack

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Solution: Recursion with memoization

Time complexity: O(2^M)

Space complexity: O(2^M)

C++

Java

Python3

Problem:

This question is the same as “Max Chunks to Make Sorted” except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), we split the array into some number of “chunks” (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Example 2:

Note:

• arr will have length in range [1, 2000].
• arr[i] will be an integer in range [0, 10**8].

Idea:

Reduce the problem to 花花酱 769. Max Chunks To Make Sorted by creating a mapping from number to index in the sorted array.

arr = [2, 3, 5, 4, 4]

sorted = [2, 3, 4, 4, 5]

indices = [0, 1, 4, 2, 3]

Solution: Mapping

Time complexity: O(nlogn)

Space complexity: O(n)

C++

Python3

Mission News Theme by Compete Themes.