JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
The Importance of Algorithms : Approximate completion time for algorithms, N = 100 | Reply
From the first topic in tutorils on topcoder I didnt understand the following thing. Can anyone explain ??

Approximate completion time for algorithms, N = 100
O(Log(N)) 10-7 seconds
O(N) 10-6 seconds
O(N*Log(N)) 10-5 seconds
O(N2) 10-4 seconds
O(N6) 3 minutes
O(2N) 1014 years.
O(N!) 10142 years.
Re: The Importance of Algorithms : Approximate completion time for algorithms, N = 100 (response to post by sdkjain) | Reply
Below is the link where I got this:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=importance_of_algorithms

Please someone reply !
Re: The Importance of Algorithms : Approximate completion time for algorithms, N = 100 (response to post by sdkjain) | Reply
It shows how long the algorithms of different complexities will take.
O(N) means basically that the time the algorithm takes to run is linearly proportional to the size of the input
O(N^2) means the time the algorithm takes to run is proportional to the size of the input squared.. etc.
Re: The Importance of Algorithms : Approximate completion time for algorithms, N = 100 (response to post by Chikov2) | Reply
Hi Chikov2,

I have an understanding of algorithms.
My doubt is about calculations mentioned i.e. when n=100 how O(n)= 10^-6 and other values mentioned.

Like if we consider 10^9 MIPS then for n=100 shouldn't it be:
O(n)= 100/ 10^9 = 10^-7 ??
and similarly for other values ??
Re: The Importance of Algorithms : Approximate completion time for algorithms, N = 100 (response to post by sdkjain) | Reply
Can anyone please explain me ??
Re: The Importance of Algorithms : Approximate completion time for algorithms, N = 100 (response to post by sdkjain) | Reply
Since O(N) does not imply performing exactly N operations, the table in the tutorial is very vague. It probably describes the running time of "light" algorithms, i.e. those with low hidden constant. In general, you can't derive the runtime from just algorithm's complexity and processor's speed.

You can interpret this table as the runtime for algorithms with hidden constant equal to 1 and processor performing 10^8 operations per second (note that yet again it depends on the type of operations, but let's keep it simple), or for algorithms with hidden constant equal to 10 and processor performing 10^9 operations per second.
RSS