This is a question from a past-yr mid-term paper from my school(using Python language). Attached below is a diagram to show how a robot will move. Don't mind if the link seems dubious as I just used an online screenshot app to make the link, can't find an online link that describes the scenario well.
From the same paper:
Basically, the robot moves forward and turns left whenever it encounters an unvisited grid square to its left. (It just keeps moving towards its immediate left in an anticlockwise direction)
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 commands. 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 briefly 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.
2)Why is the space complexity O(n^2) instead of O(n^3)? For space complexity, I used to have this impression that for recursive codes that uses some kind of slicing/concatenation would take up 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.