Python: Time and space complexity of creating size n^2 tuples

Question

This is a question from a past-yr mid-term paper from my school. Attached below is a diagram to show how a robot will move, from the same paper. My concerns are stated in the orange portion.

Basically, the robot moves forward and turns left whenever it encounters an unvisited grid square to its left.

The sequence of instructions given to the robot to transverse a size 3 gird is: ('F', 'T', 'F', 'T', 'F', 'F', 'T', 'F', 'F', 'T', 'F', 'F', 'F') where 'F' means move one square forward, and 'T' means turn 90 degrees to the left. Note that the last instruction causes the robot to exit the grid. The function gen_seq takes as input the size of a grid, and returns a sequence of instructions for the robot to transverse the grid. The sequence of instructions is a tuple containing the strings 'F' and 'T' which represent forward and turn command.

Provide a recursive or iterative implementation of the function gen_seq . Hint: Recall int can be multiplied with tuple.

State the order of growth in terms of time and space of your implementation and explain your answer.

These are the answers suggested in the markscheme.

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (n-1)*('F',)
        seq += side + side + ('F',)
    return seq

Time: O(n^3). In every function call (recursion) or loop (iteration), a new tuple of the length of the path of each “layer” of the spiral is created. Since the length of the spirals is n^2, and there are n function calls or the loop runs n times, so the total time is n^2*n = O(n3). In other words it is the sum of squares: 1^2+2^2+3^2+: : :+n^2 = O(n^3)

Space: O(n^2). End of the day, a new tuple of size n^2 is created and returned.

1)Am I right to infer that the derivation for time complexity of forming a tuple seems to be sum of length of updated tuple after every recursion/iteration.

If I want to form a tuple with size n^2(size of straightened spiral), first 1^2 has to be formed, then 2^2… n^2, leading to the above sum of squares.

I saw a related post on strings instead of tuples, in this case time= 1+2+…n=n^2, which supports my inference.

Time complexity of string concatenation in Python

2)Is it correct for me to say for space complexity of recursive functions that involve slicing/concatenation, space equal to their time, in this case O(n^3). My explanation for this case would be: Since there are n recursions that takes up space on the stack, and each recursion a new tuple of length n^2 is formed from concatenation (no slicing is seen here), space would be O(n*n^2).

I would also think the suggested space of O(n^2) only applies to iterative solutions where no stack frames are observed and only the length of the final tuple(n^2) is included in the space.

Answer 1

TLDR: Your time complexities are correct, though your O(n^3) space for the recursive gen_seq is too pessimistic (it is still significantly more wasteful). Note that the optimal static solution is O(n^2), since that is the size of the answer. If no static answer is required, space complexity can be lowered to O(1).

---

Let's start by establishing some basic complexities. The below applies to both time and space complexity:

• Creating a character literal is O(1).
• Creating a tuple of size n is O(n).
  • Creating an empty or single-element tuple is O(1).
• Concatenating two tuples of length n and m is O(n+m).
  • Concatenating two tuples of length n^2 and m, it is O(n^2+m) = O(n^2).

---

Iteration:

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (i-1)*('F',)  # note: `i-1` instead of `n-1`
        seq += side + side + ('F',)
    return seq

Key points for complexity are:

• The range(const, n+1) loop is O(n) time complexity, and O(1) space.
• The side is constructed anew at a size of n for i->n. Space is reused, for a maximum of O(n) space. Time is consumed on all n iterations, for O(n*n) = O(n^2) time.
• The seq is concatenated with an n-tuple on all n iterations. Space is reused, for a maximum of O(n*n) = O(n^2) space. Time is consumed on all n iterations, for O(n*n^2) = O(n^3) time.

The largest complexity wins, so iteration uses O(n^2) space and O(n^3) time.

---

Recursion:

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

Key points for complexity are:

• Recursion is repeated from n->1, meaning O(n) time.
• The side is constructed anew at a size of n. Space is not reused, since each side is constructed before recursion, for a maximum of O(n*n) = O(n^2) space. Time is consumed on all n iterations, for O(n*n) = O(n^2) time.
• The return value is concatenated with an n-tuple on all n iterations. Space is reused, since each return value is constructed after recursion, for a maximum of O(n*n) = O(n^2) space. Time is consumed on all n iterations, for O(n*n^2) = O(n^3) time.

The largest complexity wins, so iteration uses O(n^2) space and O(n^3) time.

---

The limit for your time complexity is that the result of each step must be repeated in the next. In Python, this can be circumvented using a generator - this allows you to return intermediate results and proceed with generating more results:

def gen_seq(n):
    yield 'F'
    for i in range(1, n):
        yield 'T'
        yield from ('F' for _ in range(i))
        yield 'T'
        yield from ('F' for _ in range(i))

seq = tuple(gen_seq(m))

Key points for complexity are:

• The range(n) loop is O(n) time complexity, and O(1) space.
• The yield from ... range(i) loop is O(n) time, and O(1) space. Space reuse leaves this at O(1) space. Repetition by n times gives O(n*n) = O(n^2) time.
• Concatenating all results at once via tuple is O(n^2 * 1) = O(n^2) space.

The largest complexity wins, so iteration uses O(n^2) space and O(n^2) time. If the result is not stored but directly used, only O(1) space is used.