Search code examples
javatime-complexityruntimecomplexity-theory

Complexity does not match the actual growth of the runtime?

I've been doing a homework sheet for a while now, and there is a massive discrepancy between what I think the asymptomatic complexity is and what the runtime result suggests.

Below is a table for the runtime for the program.

|      Input Size     |     Runtime (Seconds)   |
|---------------------|-------------------------|
|       10000         |      0.040533803        |
|---------------------|-------------------------|
|       20000         |      0.154712122        |
|---------------------|-------------------------|
|        30000        |      0.330814060        |    
|---------------------|-------------------------|
|        40000        |      0.603440983        |    
|---------------------|-------------------------|
|        50000        |      0.969272780        |    
|---------------------|-------------------------|
|        60000        |      1.448454467        |

Runtime (Seconds) Against Input Size

string = "";
newLetter = "a";
for (int i = 500; i < n; i++) {
    string = string + newLetter;
}
return string

Why would there be a discrepancy between the complexity of the algorithm and the growth of the runtime apart from me being wrong?

From the runtime results, it looks like the program has a time complexity of O(n2). Doubling the input size seems to increase the runtime by a factor of 4, which would suggest a quadratic function?

But looking at the program itself, I'm 99.9% certain that the time complexity is actually O(n).

Is it possible that there's an extraneous reason for this discrepancy? Is there any possibility that the runtime results are indeed linear?

My best guess for this discrepancy is that the for loop makes the next iteration slower (which, looking at the program makes sense as I think the Java compiler would have to iterate every additional newLetter given) but that would still be linear no? It's not a nested for loop.

Solution

  • The code you've written actually does run in time Θ(n2). The reason has to do with this part of the code:

    string = string + newLetter;

    Here, your intent is to say "please append a new character to the end of this string." However, what Java actually does is the following:

    1. Evaluate the expression string + newLetter. This makes a brand-new string formed by copying the full contents of string, then appending newLetter to the end of that new string.
    2. Assign the result to string.

    The issue here is that step (1) takes longer and longer to execute the longer the string is, since all the characters have to be copied over. In particular, if string has length k, then step (1) takes time Θ(k) because k characters must be copied. Since the length of string matches the current loop iteration index, this means the work done is

    Θ(1 + 2 + 3 + ... + n)

    = Θ(n(n+1) / 2)

    = Θ(n2),

    which is why you're seeing the plot you're seeing.

    You can speed this up by using StringBuilder rather than String to assemble the larger string. It doesn't make all the intermediary copies as it goes, and instead maintains an internal array that can grow as needed.