CODEWITHSUNDEEP
c#algorithmbig-o
void1916
void1916

Reputation: 39

Time complexity of the code below

I am trying to check the time complexity of the below simple program. The program replaces spaces in a string with '%20'.

  1. The loop to count spaces (O(1) time)

        foreach (char k in s)
    {
        if (k == ' ')
        {
            spaces_cnt++;
        }
    }

  2. The loop to replace the spaces (O(n) where n is size of string)

        char[] c = new char[s.Length + spaces_cnt * 3];
    int i = 0;
    int j = 0;
    while (i<s.Length)
    {
        if (s[i] != ' ')
        {
            c[j] = s[i];
            j++;
            i++;
        }
        else
        {

            c[j] = '%';
            c[j + 1] = '2';
            c[j + 2] = '0';
            j = j + 3;
            i++;
        }
    }

So I am guessing it is a "O(n) + O(1)" solution. Please correct me if I am wrong.

Upvotes: 0

Views: 1067

Answers (2)

Chris Gessler
Chris Gessler

Reputation: 23123

Looks like you're trying to encode a string. If that's the case, you can use the UrlPathEncode() method. If you're only trying to encode spaces, use Replace() (as mentioned by Douglas).

Upvotes: 0

Douglas
Douglas

Reputation: 54917

The loop to count spaces takes O(n), not O(1), since you’re iterating over – and performing a check on – each of the n characters in your string.

As you stated, the replacement loop takes O(n). Two O(n) operations performed sequentially have a combined complexity of O(n) (constant factors are discarded in Big-O notation).

P.S. You know that you can achieve the equivalent of all your code using a single line?

s = s.Replace(" ", "%20");

Upvotes: 6

Related Questions