Re: How to delete all nil properties from a plist?

[Emanuel Berg <embe8573@student.uu.se>]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Being O(n) doesn't come automatically by using only
> cons cdr and nreverse. It depends on the structure
> of the algorithm! http://discrete.gr/complexity/

Yes, of course. But doesn't it come automatically if
the list is iterated and there is only constant
functions in the loop body? The only thing that is
linear is the iteration of the list. If on the other
hand the body contains something that is linear as
well, as was the case with `append' and `butlast',
then it'll be linear*linear - i.e. quadratic or
O(n^2).

> NEVER put the then on the same line as the test!

... why?

> Fortunately, your loop body contains a fixed number
> of instruction, that doesn't depend on the length of
> the list or on any other value that depend on the
> length of the list. Therefore it is O(1) and O( (*
> (length l) O(1)) ) = O(length l)

"Fortune" has nothing to do with it - I knew this
algorithm was linear all the time and when you
identified the linear calls in the body I replaced
those and now the implementation is linear as well.

>> constant: cons, cdr, nreverse
>
> No. your call to nreverse is O(length l).

Since it is outside of the loop body it doesn't
change the "artificial" complexity, but OK:

    constant: cdr, cons
    linear:   append, butlast, nreverse

-- 
underground experts united
http://user.it.uu.se/~embe8573