What is the big O of this function?

PHP
1

A function that reads in a string and reverses all of the words inside of the string(the words stay in the same position, but are reversed).


function(String sentence){
  String word="";
  String reversedSentence;
  for(int i = 0; i< sentence.length; i++){
    if(sentence[i] == ' '){
        reversedSentence += reverse(word);
        word = "";
    }
    else{
      word += sentence[i];
    }
  }
}

function reverse(string s){
  String n="";
  for(int i = s.length; i >= 0; i--){
    n+=s[i];
  }
}
2

Someone is doing homework and is cheating!

3

No.

The function loops over all characters in the string sentence. So that is n operations.
Than, in that loop, for every word the function reverse is called, so that function reverse needs n - <number of spaces> operations.
Where n is the length of the original string sentence.

Now, we apply the big Oh. n-<number of spaces> operations is just O(n). The other n operations is also O(n).
So we have O(n) + O(n) or in other words O(2n). Since constants are dropped from the big Oh (unless there is nothing but a constant, in that case it will be O(1)), the end result is O(n).

4

Not sure exactly what you want. this looks like javascript, do you want it in PHP?

5

In terms of the Big Oh this would be O(n) since it’s completely linear.

However, why not use:


$newString=implode(' ', array_reverse(explode(' ', $string)));

Does exactly the same and is way shorter (and also O(n) in case you’re wondering) :slight_smile:

6

these functions don’t return anything?

7

This makes total sense to me :slight_smile: Thanks man!

8

Theoretically yes, but the 2 doesn’t count in terms of the Big Oh, so that leaves O(n). The big Oh only gives a measure of complexity and since this algorithm is in linear time, it’s O(n).

9

What about reversing the word in each string? Say reversing a word is O(k). Since we look at each character in the Sentence, that would be O(N). Wouldn’t it be some equation involving O(n) and O(k)???

10

Wouldnt it actually be 2n, given that you parse each character twice? (Once to add it to the $word, and again to reverse $word)