This is a question from a mid-term document last year from my school. Below is a diagram showing how the robot will move from the same paper. My problems are indicated in the orange part.
Basically, the robot moves forward and turns left whenever it encounters an invisible grid square to its left.
The sequence of instructions provided to the robot for crosslinking size 3: ('F', 'T', 'F', 'T', 'F', 'F', 'T', 'F', 'F', 'T ',' F ',' F ',' F ') where "F" means moving one square forward, and "T" means turning 90 degrees to the left. Note that the last command forces the robot to exit the grid. The gen_seq function takes the grid size as an input value and returns a sequence of instructions for the robot for the transverse grid. The sequence of instructions is a tuple containing the strings "F" and "T", which represent the forward and rotation command.
Provide a recursive or iterative implementation of the gen_seq function. Hint: Remember int can be multiplied by a tuple.
Indicate the growth order in terms of time and space of your implementation and explain your answer.
These are the answers suggested by 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 each function call (recursion) or in the loop (iteration), a new tuple of the path length of each spiral “layer” is created. Since the length of the spirals is n ^ 2, and there are n functions, or the cycle is executed n times, therefore, the total time is n ^ 2 * n = O (n3). In other words, this is the sum of the squares: 1 ^ 2 + 2 ^ 2 + 3 ^ 2 +: + n ^ 2 = O (n ^ 3)
Space: O (n ^ 2). At the end of the day, a new tuple of size n ^ 2 is created and returned.
1) Do I conclude correctly that the conclusion for the time complexity of forming a tuple is represented by the sum of the length of the updated tuple after each recursion / iteration.
If I want to form a tuple of size n ^ 2 (the size of the straightened spiral), first I need to form 1 ^ 2, then 2 ^ 2 ... n ^ 2, which will lead to the specified sum of squares.
I saw a related record with strings instead of tuples, in this case time = 1 + 2 + ... n = n ^ 2, which supports my output.
Python string concatenation temporary complexity
2) Is it right for me to talk about the spatial complexity of recursive functions, which include slice / concatenation, a space equal to their time, in this case O (n ^ 3). My explanation for this case would be the following: since there are n recursions on the stack that occupy a place on the stack, and each recursion is formed from a new set of roots of length n ^ 2 (without slicing) here will be O (n * n ^ 2).
I also think that the proposed space O (n ^ 2) is applicable only to iterative solutions in which stack frames are not observed, and only the length of the finite set (n ^ 2) enters the space.