Re: Quicker Array Searching

As can be seen, this is going to run in O((n-1)!)

I think that's actually O(N^2) which, although not blazingly fast, is much, much faster than O(N!).

-sauoq
"My two cents aren't worth a dime.";

Comment on Re: Quicker Array Searching

Replies are listed 'Best First'.
Re: Quicker Array Searching by jonadab (Parson) on Oct 29, 2003 at 21:37 UTC
I think that's actually O(N^2) You may be right; I wasn't careful with my analysis of the speed of the algorithm, other than in terms of how to improve it. which, although not blazingly fast, is much, much faster than O(N!) No joking. `$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}} split//,".rekcah lreP rehtona tsuJ";$\=$ ;->();print$/` [download]	[reply] [d/l]
Re: Re: Quicker Array Searching by sauoq (Abbot) on Oct 29, 2003 at 21:38 UTC
No joking. Heh. Nevermind 7000 messages... 17 would be intractable. :-) -sauoq "My two cents aren't worth a dime.";	[reply]
Re: Quicker Array Searching by jonadab (Parson) on Oct 29, 2003 at 21:51 UTC
Nevermind 7000 messages... 17 would be intractable. Perhaps I neglected to mention that I once wrote a recursive brute-force program and, being careless because I knew n would never be more than 20 or so, inadvertently wrote it in such a way that it not only ran in O((n^2)!) time, but also used (n^2)! RAM. Err, well, (n^2)! swapfile space, actually. It worked okay for n=3, but when I tried to run it for n=4... let's just say I don't recommend this technique. `$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}} split//,".rekcah lreP rehtona tsuJ";$\=$ ;->();print$/` [download]	[reply] [d/l]