-1

Assume that there is a question where a string needs to be passed. Some modification needs to be done on the string and then returned back.

For the programming languages like C where a string is a character array, making the modifications, swapping characters is not a problem as all of them can be done in place.

But for programming languages like Python, making in place modifications, or swapping characters is not that straightforward.

Hence I convert the string to a list, and then do the modifications and then make the string back and return.

The question is: Will the conversion of a string to a list and back count in time complexity in interviews.

3
  • 2
    you'd have to ask the interviewer. But i would say no. Or perhaps simply change the input to the function you are writing
    – Ewan
    Commented Apr 3, 2021 at 11:36
  • 2
    You should talk you way thru it. If you pass a string with twice as many characters in it, will the time taken by your function be the same, or twice as long? Explain your reasoning to the interviewer. Commented Apr 3, 2021 at 15:11
  • "... is not that straightforward." It depends on the use case you have in mind. Could you elaborate on why you're converting it to a list?
    – J.G.
    Commented Apr 3, 2021 at 16:29

1 Answer 1

1

The simple answer is: it depends.

It doesn't make sense to talk about "time complexity". You always talk about time complexity within a specific machine model and with a specific cost model.

The machine model tells you which operations exist, the cost model tells you how expensive each operation is.

Just as an example why the machine model is important: in a Turing Machine, copying a list takes θ(n2) operations, in a Random Access Machine, it takes θ(n), where n is the number of elements in the list.

Next, you have to specify how you define the "size of the input". In other words: what is "n"? For example, we normally take "n" to mean the length of the input. That means for example that for numbers, "n" is not the number, but the logarithm of the number.

You also need to specify whether you are talking about worst case, best case, amortized worst case, average case, or expected case. And lastly, you need to specify whether you are talking about time complexity or step complexity. I know that your question explicitly says "time complexity", but actually, I have found many people saying "time complexity" and then when asked for a definition, they supply the definition for step complexity.

So, to recap: the answer to whether or not to count this depends on whether your model says to count this.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.