[lkml]   [2001]   [Feb]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [rfc] Near-constant time directory index for Ext2

    > Not true. The rehashing is O(n) and it has to be performed O(log n)
    > times during insertion. Therefore, insertion is O(log n).

    Rehashing is O(n), but the "n" is the _current_ number of items, not the
    maximum one after all the insertions.

    Let's assume you start with a single-entry hash table. You rehash for the
    first time after inserting the first item (giving hash table of size 2),
    then after the second item (=> size 4), then after the fourth item (=> size 8)
    and so on. I.e., when you insert n items, the total cost of rehashing summed
    over all the insertions is at most 1 + 2 + 4 + 8 + 16 + ... + 2^k (where
    k=floor(log2(n))) <= 2^k+1 = O(n). That is O(1) operations per item inserted.

    Have a nice fortnight
    Martin `MJ' Mares <> <>
    MIPS: Meaningless Indicator of Processor Speed.
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:17    [W:0.020 / U:5.980 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site