Neccesary Algorithm Complexity

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
The^Guard
New poster
Posts: 6
Joined: Wed Nov 23, 2005 11:16 pm

Neccesary Algorithm Complexity

Post by The^Guard »

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) ?

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 »

"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. :)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

Post Reply

Return to “Algorithms”