Suppose you have a population of N individuals with fitness 1, 2, . . . , N (i.e., all individuals have a unique fitness value). Suppose you repeatedly apply tournament selection without replacement with tournament size s = 2 to this population, without doing crossover, mutation, and replacement.

In other words, you run a genetic algorithm with selection alone. After a certain number of generations you will end up with a population consisting of N copies of the same individual. Can you give an estimate of the number of generations needed to achieve that?

Is the answer to this just log(n) ?


1 Answer 1


The complexity of one generation will be O(N/2). In order to make the whole population the same, you will need N generations. My answer will be O(N**2).

You can also evaluate the time complexity by actually measuring the run time and averaging.

If you don't do crossover, mutation or replacement you are just selecting the best of your individuals.

  • $\begingroup$ yes. but using tournament selection without replacement, how many generations would it take to get a population consisting only by the same individual repeated N times? $\endgroup$
    – ruben
    Commented Dec 20, 2019 at 12:01
  • $\begingroup$ I edited the original answer. $\endgroup$ Commented Dec 20, 2019 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.