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


Answer: 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)`.

