## Issue

I don’t understand how these two implementations generating the look and say sequence have different times of execution because they perform really similar operations but more I increase `n`

more the time difference between the two codes is bigger .

The `Big O`

of the two algorithms is the same because the while loop in the first one iterates `n`

times as the for loop in the second one and the nested for loop in the first one scans all elements as the two nested while loops in the second one.

this is the first one :

```
def look_and_say_sequence(first, n):
while n != 1 :
succ, start, k = '', first[0], 0
for x in first :
if x != start :
succ, start, k = succ + str(k) + start, x, 1
else :
k = k + 1
first = succ + str(k) + start
n -= 1
return first
look_and_say_sequence('1', 48) # 10 SECONDS
```

and this is the second one :

```
def look_and_say_sequence(first, n):
for _ in range(n-1):
seq, res, ind = first, '', 0
while ind < len(seq):
pending, c = seq[ind], 0
while ind < len(seq) and pending == seq[ind]:
c += 1; ind += 1
res += "{}{}".format(c, pending)
return res
look_and_say_sequence('1', 48) # 2 SECONDS
```

So, how can it be that there is a factor of 5 between the two implementations?

Thank you for the help!

## Solution

Your slowdown lies in the line

```
next_element , start , k = next_element + str(k) + start , x , 1
```

which causes major runtime losses when next_element is a very long string (as certainly becomes the case as n grows large – next_element is over 500k characters long for n = 48). Try running the following two scripts:

```
import time
a = time.time()
s = ''
for i in range(99999):
s = (s + '1') + '1' # comment this out
# s += '1' + '1' # and uncomment this to see the speed difference
b = time.time()
print(b-a)
```

you’ll notice using the line using += runs dramatically quicker. Python evaluates left-to-right, meaning the `(s + '1')`

has to evaluate out to a new string before appending the `+ '1'`

. This is what adds so much slowdown.

fwiw if you change that problem line to

```
next_element += str(k) + start
start = x
k = 1
```

you’ll actually see your top algorithm runs faster

Answered By – Areeb Malik

Answer Checked By – Gilberto Lyons (BugsFixing Admin)