This question stems from this question and this answer. I also want to preface this question by stating that this question is done from the perspective of a RAM (or PRAM if it's more accurate term) model.
From the comments in the answer, it seems like when doing algorithm analysis for the solution:
- $O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction.
for the problem of:
finding the number that is different between two arrays (I'm assuming a fixed size structure, if it matters) of unsorted numbers (paraphrased by me)
that it isn't as black and white as just coming to the conclusion as $2n$ (1 pass for each array), because you have to take into account the size of the number too. That is the part I am confused about. I've asked one of the commenters to elaborate a bit more for me:
My idea is that while the time to add two numbers is proportional to their length, but there are $O(\log n)$ extra bits that the partial sums have over the longest input. Now, there are two things that complicate things. First, the inputs need not have the same length, but we'd like complexity in terms of their total length. If your addition is proportional to the longer number, you might rack up $O(n^2)$ quite easily. The solution is to add in place, which means the addition is proportional to the addend length - if not for carry. Now you just need to find how many carries you can have.
Despite this pretty detailed comment, I'm still having difficulty understanding why it's different. (I suspect the reason is due to my ignorance of the lower level ongoings of a computer and numerical representations). Not wanting to test their patience, I googled it and asked here, but unable to properly articulate the question, the most I found was this answer, which seems to echo the quote above (I think), thus didn't help me further.
Is it possible to simplify the explanation by perhaps illustrating it or elaborating further? Or is this as simple as it can get (and I just need to get the prerequisite knowledge)?