4 ms·
> It takes O(n*n) time to add the n integers. Eh?
by dirtydroog 7y ago
> It takes O(n*n) time to add the n integers.
Eh?
- saagarjha 7y agoThe time complexity assumption for addition is given earlier in the article.
- polyphonicist 7y agoFrom the article: > We will be dealing with arbitrary precision integers (bignums) in the problem, so let us also make a few assumptions: > Addition or subtraction of an m-bit integer and an n-bit integer (m <= n) takes O(n) time. > Counting the number of 1-bits in an n-bit integer takes O(n) time.