What is a quadratic process?

Question

I was reading the Go programming language book (by Donovan and Kernighan) and about their example echo1, they said: "This is a quadratic process that could be costly if the number of arguments is large, but for echo, that's unlikely". What does quadratic process mean?, and how is it costly if the number of arguments is large?

Thanks.

Cultch

@KenWhite, I am pretty sure what quadratic means. But in this example, and in programming in general, what does quadratic process mean? And how does it affect performance? If you have a link to that, I would appreciate it. Thanks! – Cultch

Answer 1

Generally speaking quadratic means something that pertains to squared numbers. In this context it means that the cost of the process is proportional to the square of the input size. This is because strings are concatenated using += operator which is expensive in Go as strings are immutable and a new string must be created in memory every time you concatenate. More efficient ways to concatenate strings include writing to bytes.Buffer and converting it to string, or using strings.Join function

Elemi

Thanks @jussius. I understand now! And this is exactly what is discussed later in the book. And the cost here is memory-wise I assume? – Cultch

More or less. Lets say you were appending "Hello" and "World" using `s = "Hello" + "World". You would create a new rune array 10 runes in length, then copy "Hello" into the first half, and "World" into the second. Fairly easy. – Snowbound

However, if you expand this to say concatenating "H", "e", "l", "l", "o", "W", "o", "r", "l", and "d", and you were still using the + (or +=) operator, now we have an issue. You start with "H" + "e", make a new array of length 2, copy in "H" and "e". Now you have "He" + "l". New array of length 3, copy in "He" and then "l". Repeat until you're out of strings. You're creating a new array each time, because strings are immutable, so concatenation has to make a new string, and thus a new underlying array. This means a LOT of allocation and copying, especially for the earlier strings. – Snowbound

Thanks @Kaedys, that's what I understood from the answer above. But your example "Hello" + "World" example was much required! – Cultch

So, in BigO terms, the for loop is O(N) and, because string concatenation requires a new string to be created every time the loop runs (and because array creation also has O(N) complexity), therefore the program has O(N^2) complexity? – Tumulus

@Tumulus Well, you could say that the whole program is just a single for loop, so the loop (i.e. the program) has O(n^2) complexity. Easy way to think of it is that if you double the number of arguments, it means you have to create twice as many strings, but it also means the average length of the strings you're creating is twice as long (and thus, twice as costly). So in total you have to do 4 times as much work. – Elemi

@Elemi A loop doesn’t have O(n^2) complexity just because it’s a loop though :P it could just contains instructions that are O(1), making its complexity O(N) – Tumulus