OJ Board

I wonder if there is a way to find out the neccesary algorithm complexity for scoring full score on some problem, if you know the computer speed (operations per second), and the size of the input of the problem...

For example, if we have P4 (3 Ghz = 3 billion operations/second), and the maximum size of N is 3 billion, will the program pass with a linear algorithm O(N)... I found out that it'll not, but I don't know why, and because it can't, what compexity is neccesary -O(logN) ?

"3 Ghz = 3 billion operations/second" is not a correct interpretation, it should be 3 billion cycles/second and it is the system's clock speed but not all operations necessarily take 1 cycle, only the very basic operations can be done in a cycle but the operations that we do in our codes (mod or multiplication or memory access from a large array) usually are combination of several basic operations which together requires a number of cycles. To be more precise, only the (op-code) fetch cycle is fixed for a processor but the execution cycle varies widely depending on the instruction to be executed.

Hope it helps.

Just a note: you usually have to read the input..