Hello, In https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007549e5#analysis, at the bottom of the analysis it says:
"All the checks performed above are linear in the length of A and B and each number in the input is processed at most once as A and at most once as B. However, numbers may become longer after each operation, but only by 1 digit. Therefore, the complexity of the overall algorithm is quadratic in the total number of digits in the input, and linear in the number of digits of the output." I do not understand why it says "quadratic in the total number of digits in the input". Shouldn't it be O(N*(D+N)) with D the digit length of the highest integer in the input? Let's take the worst case where we have 100 numbers which are all equal to 10^9. Then roughly the most expensive operation is the last one where both A and B are close to 10+100 = 110 digits. So the highest length is close to D+N and since we have 100 operation that are at most O(D+N), we have O(N*(D+N)), with N*(D+N) around 10^4 in this case. On the other hand, if it were quadratic in the total number digits of the input (which is 100*10 = 10k) it would mean in that case that something would be linear of 10_000^2, which is 10^8, which is way bigger than 10^4. Is there an error or is there something that I misunderstood? -- -- You received this message because you are subscribed to the Google Groups Code Jam group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at https://groups.google.com/d/forum/google-code?hl=en --- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/6b30de3d-d5c9-4564-acd3-0fa6562c240fn%40googlegroups.com.
