What is the Big-O of this function that reverses words in a string

Question

I have a simple function, reverseWords(), that reveses the words in a string. eg. an input of a S = "this is a string" gives an output of "siht si a gnirts"

I was wondering what the big O of this function is. Is it O(N), O(N^2), or O(N* M)?

def reverseWords(S):
    # code in Python 2.7
    listA = S.split()
    output = []
    for element in listA:
        output.append(element[::-1])

    return (" ".join(output))

Is it O(N), O(N^2), or O(N* M)?

O(N^2) because we have a nested loop eg. passing over input once, outer loop, and then reversing each character as the inner loop
O(N*M) same reason as above except M is denoted as the looping over the characters
O(N) because... I forgot the explanation

The most entertaining way to find the answer to this question is to create various sample inputs and test it. :) — TigerhawkT3, Jun 22 '15 at 20:50
Hint: `reverse` is O(N) and looping is O(M) (M is the length of `listA`)! — Mazdak, Jun 22 '15 at 20:52
related: [Efficiently reverse the order of the words (not characters) in an array of characters](http://stackoverflow.com/q/47402/4279) — jfs, Jun 23 '15 at 08:01

Steve Jessop · Accepted Answer · 2015-06-22T21:16:11.693

It's O(N). I assume the part you're unsure about is:

for element in listA:
    output.append(element[::-1])

The thing to note here is that although we do have nested loops (over listA and over the characters in each element of it), the total number of characters processed is still only O(N). If k is the average number of letters in each word, then you can think of the time as N/k (for the outer loop) * k (for the inner loop) = N.

A more direct (I'd say better) way to analyse it is to think, "what do I need to do for each character"?:

scan over it looking for word boundaries in split()
copy it to a new string in split()
append that new string to a result list (actually we do this less than once per character, but an upper bound is fine for big-O)
advance the iterator over listA (again, less than once, only once for each word)
copy it in reverse order into a new string in the slice.
append its containing string to output (once for each word)
whatever join() does (which I invite you to investigate if you care, or take my word that it's O(total length of all strings)).

Therefore, provided that the list appends, memory allocation, and whatnot, are all amortised O(1), which in CPython they are, then the overall time complexity is O(N) including the join().

And since correct terminology is important, since it's O(N) it therefore is also O(N^2).

What is the Big-O of this function that reverses words in a string

1 Answers1