News for hackers. Stuff that matters.

A comment on From Tower of Hanoi to Counting Bits (2011).

Re:From Tower of Hanoi to Counting Bits (2011) by dirtydroog on Saturday February 29, 2020 @08:05AM (#22450344)
> It takes O(n*n) time to add the n integers.

Eh?

[ Parent | on HN ]
Re:From Tower of Hanoi to Counting Bits (2011) by saagarjha on Saturday February 29, 2020 @08:18AM (#22450378)
The time complexity assumption for addition is given earlier in the article.
[ Parent | on HN ]
Re:From Tower of Hanoi to Counting Bits (2011) by polyphonicist on Saturday February 29, 2020 @10:08AM (#22450901)
From 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.

[ Parent | on HN ]