big O notation of PE problems

General chat, humour, riddles, logic/lateral/word puzzles...
Post Reply
s4mp
Posts: 5
Joined: Sat Apr 25, 2020 6:28 pm

big O notation of PE problems

Post by s4mp »

I'm a bit confused identifying the big O notation of project euler problems, to be specific problem 62

I have a solution using only 1 for loop, but it doesn't grow linearly with the input value (being the number of permutations) As the amount of primes you have to search through increases, not related to the algorithm though

Is it even possible to give a big O notation value to this algorithm?
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: big O notation of PE problems

Post by pjt33 »

The subject of asymptotics confuses many people, and often needs careful statement to avoid confusing the rest.

Big-O notation is a notation, that is to say, a representation. The representation is not the same as the thing it represents, which is the asymptotic behaviour of something.

A statement that a problem is in a complexity class defined by an asymptotic bound on execution time (e.g. "Problem 1 is in O(lg n)") is a statement about the existence of an algorithm. Problem 1 is in O(lg n) iff there is any algorithm for problem 1 which runs in O(lg n) time. So an algorithm for the problem only gives a bound on the complexity of the problem.

There's also a pedantic point that you have to identify the variables. Before we can say that Problem 1 is in O(lg n) we have to restate it as "Find the sum of all the multiples of 3 or 5 below n".

For problem 62, I assume that by "input value (being the number of permutations)" you mean that you're restating it as "Find the smallest cube for which exactly n permutations of its digits are cube". It's not obvious that such a cube necessarily exists for all positive integers n; proving that it does would be the first step towards determining the complexity of the problem.
s4mp
Posts: 5
Joined: Sat Apr 25, 2020 6:28 pm

Re: big O notation of PE problems

Post by s4mp »

Correct assumption, that was what i meant by the variable.

i'm not really sure i would be able to calculate the time complexity, thats a bit above my level. Although i can tell its not what i originally thought it was, as its dependant on permutations. Definitely not as simple as i thought!

edit: Do you know of any problems < 100 where the time complexity can be easily calculated?
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: big O notation of PE problems

Post by pjt33 »

s4mp wrote: Tue Sep 22, 2020 6:56 pm edit: Do you know of any problems < 100 where the time complexity can be easily calculated?
I know of some where it can be upper-bounded, but giving the bounds would be a partial spoiler for the solution. (In fact, once you've done a couple of hundred problems the size of the input often gives you hints about how to solve the problem).
Post Reply