CODEWITHSUNDEEP
algorithmtime-complexity
gizgok
gizgok

Reputation: 7649

Running time analysis for addition of two n digit numbers

I'm trying to see what is the time complexity of addition of two numbers. It is written here as addition being n square. Algo Notes

Page number 4 second paragraph.

Now if I take 99 + 99 as I 'll be doing two addition operations and two carry operations + adding carry from prev to new result and combining everything.

I'm not sure how can I say this is n square.

That makes me think that I should possibly represent the numbers in binary which would make 01100011 in 8 bits which would lead to 8 additions plus 4 carry additions. This seems like n square but I'm not sure about it.

Is there a different way to look at this? How is it n square? You can run a loop over each digit and add the positional place i.e 10*sum+100*sum etc, but I can very well do this in one single for loop.

Upvotes: 0

Views: 4285

Answers (1)

rici
rici

Reputation: 241861

The sentence you refer to says:

Addition isn’t free, either. Adding two n-digit numbers takes O(n) time, so the running time of the iterative algorithm is O(n2).

I bolded the relevant words which you might have missed the first time you read the text.

"The iterative algorithm" referred to is an algorithm for something else being discussed in the previous pages, not for adding two n-digit numbers.

Upvotes: 3

Related Questions