Re^6: Algorithm complexity

Lets suppose a brute-force algorithm testing all numbers up to n. (don't wanna complicate it by restricting it to primes)

After a week and testing 10^x numbers you'll get 2 correct Wieferich primes and the information that calculating a third prime bigger than 10^x takes at least 10^x steps.

That's an empiric lower bound for the complexity, you can tell that this brute-force approach is at best O(n) for n<10^x, which is quite accurate!

OK, this example is a little bit too trivial, since it's a decision problem.

You actually have 10^x points and not only 2 !

Cheers Rolf

Comment on Re^6: Algorithm complexity

Replies are listed 'Best First'.
Re^7: Algorithm complexity by spx2 (Deacon) on Jul 08, 2009 at 11:11 UTC
no you don't . since 1940 until 2005 they have only been able to check all pairs up to 1.25 x 10^15 and it turned out there was only one pair of such numbers . please notice that it took 65 years and they did not find another one , so it's not a matter of weeks/months .. it's almost 7 decades.	[reply]
Re^8: Algorithm complexity by LanX (Saint) on Jul 08, 2009 at 11:27 UTC
Did I say x==15 ??? Does x have to be 15 to suppose it's a hard problem? Please note those "checks" in the referenced article were done with a computer and not with pure mathematical proving! And this computer wasn't build "65 years" ago! Better find another problem this one is a boomerang. 8) Cheers Rolf	[reply]