logoalt Hacker News

floxy • yesterday at 4:40 AM • 1 reply • view on HN

             1234567890 
           x     111111
           ------------
             1234567890
            12345678900
           123456789000
          1234567890000
         12345678900000
      + 123456789000000
      -----------------
    137,174,072,825,790
...looks like O(n^2).

Replies

ccleve • yesterday at 4:59 AM

Once the longer number starts repeating digits, then it's not n^2 anymore. Multiplies get replaced with lookups. And we're only counting the multiplies. That's all they counted in the article. Not the adds, not the shifts.

➕ show 3 replies