CSC300 / CSC402: RelativeGrowth [7/7] Previous pageContents

Let t2 = 1 + 2 + 4 + 8 + 16 + ... + N

Let p1 = 0 + 1 + 2 + 3 + 4 + ... + N

            N             t2                   p1
    ---------------------------------------------
            1              1                    1
            2              3                    3
            4              7                   10
            8             15                   36
           16             31                  136
           32             63                  528
           64            127                2_080
          128            255                8_256
          256            511               32_896
          512          1_023              131_328
        1_024          2_047              524_800
        2_048          4_095            2_098_176
        4_096          8_191            8_390_656
        8_192         16_383           33_558_528
       16_384         32_767          134_225_920
       32_768         65_535          536_887_296
       65_536        131_071        2_147_516_416
      131_072        262_143        8_590_000_128
      262_144        524_287       34_359_869_440
      524_288      1_048_575      137_439_215_616
    1_048_576      2_097_151      549_756_338_176

Quadratic growth is pretty bad!

Previous pageContents