# What is the time complexity of this method?

On CodingBat.com there's a problem that asks for the length of the longest sequence of repeating characters within a string:

Given a string, return the length of the largest "block" in the string. A block is a run of adjacent chars that are the same.

maxBlock("hoopla") → 2

maxBlock("abbCCCddBBBxx") → 3

maxBlock("") → 0

This is the solution I wrote:

public int maxBlock(String str) {

int max = 0;

for(int i = 0; i < str.length(); i++)
{
char c = str.charAt(i);
int j = i + 1;
int possibleMax = 1;

// iterate through a "block"
while(j < str.length() && str.charAt(j) == c)
{
possibleMax++;
j++;
}

// if the block's length is greater than any found, save it
if(possibleMax > max)
max = possibleMax;
}

return max;
}


The time complexity is at least O(N) but I'm not sure if the while loop inside makes it O(N^2).

• Suppose that you will run your program on "aaaaaaa". How many times will j++; be executed? Can you speed up your program? Apr 25, 2019 at 2:42
• @Apass.Jack Yeah, so I added " i = j - 1; " right after the while loop so that after it goes through a sequence of repeated letters, it doesn't try again for each letter, but skips to the end of that sequence. Apr 25, 2019 at 2:54

The worst-case time complexity is $$O(n^{2})$$.
Consider the example string "aaaaaaaaaa" — that is, 10 'a's. This happens to be the worse case edge scenario, because j++ has to run for every remaining character in the string, at every position. When i=0, the while loop will run 9 times; when i=1, 8 times; so on until when i=N-1, the loop runs 0 times. Therefore, the total number of times the while loop has to run (over all i) is given by the sum from 0 to N-1, which, with arithmetic series, is $$S = \frac{N}{2}(N-1)$$. This simplifies to $$\frac{N^{2}-N}{2}$$; however, when writing time complexity with big-O notation, we ignore constant or slower-growing factors. Therefore, as $$N$$ grows asymptotically large, the total time complexity reduces to $$O(N^{2})$$, although in reality it is something closer to $$O(\frac{N^{2}}{2})$$.
Another way to look at it is that the outer for loop runs exactly $$N$$ times, and the number of times the inner while loop runs does depend on $$N$$ (and linearly at that), so the time complexity must be at least greater than $$O(n)$$.
• "Another way to look at ... so the time complexity must be at least greater than $𝑂(n)$." Not that it is wrong. However, the logic is not smooth. Had you said "the outer for loop runs exactly $N$ times, so the time complexity must be at least $O(N)$", that would be smooth. Apr 25, 2019 at 4:48