0
$\begingroup$

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:

enter image description here

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.

https://stackoverflow.com/questions/37133547/time-complexity-of-string-concatenation-in-python

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.

$\endgroup$
  • $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Mar 28 '18 at 10:05
  • $\begingroup$ Python is offtopic here, algorithm analysis is ontopic. Please make up your mind what you're asking about: analysis of the given algorithm, or details of Python library implementations? $\endgroup$ – Raphael Mar 28 '18 at 10:08
  • 1
    $\begingroup$ Note that SE only supports image links using HTTPS. It's easiest to just use the built-in uploader (to Imgur). I did it for you this time; please be more proactive next time. Also, you need to give attribution to the source of that graphic! $\endgroup$ – Raphael Mar 28 '18 at 10:09
  • $\begingroup$ @Raphael I have the following concerns. 1) the original source of my question was from an exam paper tested in a specific language 2)analysis of algorithm might be related to some processes supported by the language(for eg tail call optimisation) 3)The algorithm is used in a weird context and I don't know how to extract accurate pseudocode from it without clarifying myself later. 4)I have an answer in mind and I want to verify it, do I have to explain my answer? If my question falls under the above categories, how should I frame my question? $\endgroup$ – Prashin Jeevaganth Mar 28 '18 at 10:35
  • 1
    $\begingroup$ 1) If the exam is about Python, it's for Stack Overflow. If the exam is about algorithms but specifics of Python are relevant, your teacher has ... interesting opinions. 2-3) If that's the issue, I don't think this is the place for this question. You should talk to your teacher. 4) If you can show your work and as a specific question about it, that would be great. "Is this correct?" is not such a question. $\endgroup$ – Raphael Mar 28 '18 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.