4

I have written different python codes to reverse a given string. But, couldn't able to figure the which one among them is efficient. Can someone point out the differences between these algorithms using time and space complexities?

def reverse_1(s):
      result = ""
      for i in s : 
          result = i + result
      return result

def reverse_2(s): 
      return s[::-1]

There are already some solutions out there, but I couldn't find out the time and space complexity. I would like to know how much space s[::-1] will take?

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219
Venkata Gogu
  • 1,021
  • 10
  • 25
  • `reverse_1` is the worst reverse routine you can possibly write. With `O(n*2)` complexity. Stick to the second one which is `O(n)` and doesn't use a loop – Jean-François Fabre Jul 14 '18 at 05:14
  • But, what if the interviewer doesn't accept it. It's kind of cheating. Is there any other way to reverse a string in python. – Venkata Gogu Jul 14 '18 at 05:17
  • A suggestion for a quick test is use timeit feature from ipython console. This way: `timeit reverse_1('blabla')`. – Lorran Sutter Jul 14 '18 at 05:17
  • @Jean-FrançoisFabre `O(n + n)` is the same as `O(n)` – smac89 Jul 14 '18 at 05:21
  • @VenkataGogu if using best features of python is cheating then I don't know... you can boast with alternatives like I provided in my answer, & the argumentation. I doubt an interviewer would object that. – Jean-François Fabre Jul 14 '18 at 05:22
  • @smac89 yes and? the join method is O(n) but is still slower than the slice method. – Jean-François Fabre Jul 14 '18 at 05:23
  • @Jean-FrançoisFabre, so it can't be worse than `O(n)` as per your comment – smac89 Jul 14 '18 at 05:23
  • @smac89 `reverse_1` is worse: it's `O(n*n)`. Try that on a really large string, it never ends because it has to copy the string. So basically `n*(n-1)//2` copies – Jean-François Fabre Jul 14 '18 at 05:25
  • @Jean-FrançoisFabre, you wrote `O(n * 2)` no? Maybe you mean `O(n ^ 2)`? Anyways, you're right, `O(n*n)` is worse than `O(n)` – smac89 Jul 14 '18 at 05:27
  • @smac89 ah you're right, my bad. I meant n*n or n^2. I had to close as duplicate, after reading the original question & answers, though. – Jean-François Fabre Jul 14 '18 at 05:28
  • @Jean-FrançoisFabre, why is this question duplicate? I have already seen that post before posting my question. All answers said `s[::-1]` is a way but never mentioned the time and space complexity for that statement. – Venkata Gogu Jul 14 '18 at 05:38
  • I'd very much like this question _not_ to be a duplicate (I answered it) but if you read the answer of the other question, you notice that my answer just sums up what is said here, and comes to the same conclusions. Maybe you could edit to explain why it isn't a duplicate. I'd very much like to reopen but I feel that this isn't appropriate ATM. – Jean-François Fabre Jul 14 '18 at 05:42
  • Yes, obviously to test this, I can use `timeit` to know which one function works great. But, key factor for me is space which never mentioned in that post. – Venkata Gogu Jul 14 '18 at 05:44
  • edited my answer to reflect the space complexity aspect – Jean-François Fabre Jul 14 '18 at 06:03

1 Answers1

7

Without even trying to bench it (you can do it easily), reverse_1 would be dead slow because of many things:

  • loop with index
  • constantly adding character to string, creating a copy each time.

So, slow because of loop & indexes, O(n*n) time complexity because of the string copies, O(n) complexity because it uses extra memory to create temp strings (which are hopefully garbage collected in the loop).

On the other hand s[::-1]:

  • doesn't use a visible loop
  • returns a string without the need to convert from/to list
  • uses compiled code from python runtime

So you cannot beat it in terms of time & space complexity and speed.

If you want an alternative you can use:

''.join(reversed(s))

but that will be slower than s[::-1] (it has to create a list so join can build a string back). It's interesting when other transformations are required than reversing the string.

Note that unlike C or C++ languages (as far as the analogy goes for strings) it is not possible to reverse the string with O(1) space complexity because of the immutability of strings: you need twice the memory because string operations cannot be done in-place (this can be done on list of characters, but the str <=> list conversions use memory)

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219