PythonとPyPyで文字を追加する速度が全然違う

AlignmentのBacktrackのときに、文字を前に追加しなければならないが、当然後ろに追加して最後に文字列を逆にする方が速いと思える。

しかし、このようなコードで、

import sys
import time

def f_add_to_head(N):
	s = ''
	for _ in range(N):
		s = 'c' + s
	return s

def f_add_to_tail(N):
	s = ''
	for _ in range(N):
		s = s + 'c'
	return s[::-1]

t0 = time.clock()
N = int(sys.argv[1])
f_add_to_head(N)
print >>sys.stderr, time.clock() - t0
t0 = time.clock()
f_add_to_tail(N)
print >>sys.stderr, time.clock() - t0

PythonとPyPyで速度が全然違った。

$ python add_head.py 300000
6.40625
0.015625

$ pypy add_head.py 300000
4.03125
4.0

ここで、pythonは2.7.15で、printを修正したPython3.6.8でも変わらなかった。
Pythonでは、前に追加の場合、O(N^2)より遅く、後ろに追加の場合、O(N)のようだった。PyPyはともにO(N^2)のようだった。