Date: 03/26/05 (Algorithms)    Keywords: database

Hi all, I attempt to show an example of heuristic based algorithm such as Genetic Algorithm runs in polynomial time, my analysis is below. Please give comments as I feel that the way I write it is not very clear and possibly can contain technical errors.  Thank you in advance. 

  


    Approximation algorithms such as Genetic Algorithm takes polynomial time.  It is O(G) where G is the number of generation.
       
    The most important and time consuming part in each generation is probably the fitness evaluation since all chromosomes are tested against the database (tvn note: in this GA example the chrome fitness is tested against a DB).  The time for each individual chromosome to process an entire database of size D, where D is the number of column and R is the largest row, is at worst (max(D,R))^2 or O(max(D,R)), still polynomial time.  Of course, each chromosome will be tested against the database so it would be the population size * the time to process the entire database for each in
dividual.
        There are other operations in each generation such as the cross-over and mutation, but the run time for these two operations per chromosome is either constant or at most O(n) where n is the number of genes in a chromosome.
       

Source: http://www.livejournal.com/community/algorithms/50976.html