## Tuesday, August 9, 2011

### Algorithm and its Runtime Analysis

Algorithm: An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output.

Simple Algorithm

Run-time algorithm specialization is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. The methodology originates in the field of automated theorem proving and, more specifically, in the Vampire theorem prover project.One of the most important aspects of an algorithm is how fast it is. It is often easy to come up with an algorithm to solve a problem, but if the algorithm is too slow, it's back to the drawing board. Since the exact speed of an algorithm depends on where the algorithm is run, as well as the exact details of its implementation, computer scientists typically talk about the runtime relative to the size of the input.

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.