What is the Big O Note for str.replace function in Python?

Question

What is the biggest notation for str.replace in Python?

Is it always O (n)?

 str = "this is string example" print str.replace("is", "was") 

 thwas was string example 

Answer 1

The Big O designation is calculated in the worst case, and Python sources for the worst case simply "find the next substr position, replace, and move on." One replacement performs O (n) operations (copying a string). One search, according to http://effbot.org/zone/stringlib.htm , performs O (n * m) operations in the worst case. And since it can be up to n / m replacements, overall it should be surprisingly O (n * n).

Answer 2

I coded a test for what, in my opinion, is the worst case scenario - a repeating line is repeated over and over, and we replace the specified line with another line. As t/n aligns as n increases, the worst-case scenario seems empirical, as if it could be O(n) . But I really can't argue with the @NickolayOlshevsky post.

 import time from matplotlib import pyplot as plt x=[10] while x[-1]<10**8: x.append(int(x[len(x)-1]*1.5)) y = [0]*len(x) nst = 'abcd' sst = 'abcd' for ix,i in enumerate(x): s = ''.join([nst]*i) t = time.time() s = s.replace(sst,'efgh') y[ix] = time.time()-t x = [a*len(nst) for a in x] %matplotlib inline fig, (ax1,ax2) = plt.subplots(2, sharex=True) fig.set_size_inches(8, 6) ax1.set_xscale('log') ax1.set_yscale('log') ax1.set_xlabel('n') ax1.set_ylabel('t') ax1.plot(x,y) ax2.set_xscale('log') ax2.set_yscale('log') ax2.set_xlabel('n') ax2.set_ylabel('t/n') ax2.plot(x,[a/b for a,b in zip(x,y)])