Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the divide and conquer algorithmic paradigm. Some algorithms we have studied/I have read about are mergesort, max subarray problem, Strassen's algorithm etc.

When analyzing a lot of these algorithms, a simplifying assumption is generally made that the input size is a power of 2 - thus finding time complexity assuming input size is a power of 2. Surely this cannot constitute a general proof because of this assumption?

  • $\begingroup$ This link has what you are looking for - they give a proof of why this is done and in what cases is this feasible. $\endgroup$
    – Gokul
    Nov 17, 2018 at 16:58
  • $\begingroup$ The question was already asked and answered on this site. Perhaps somebody can find the link. $\endgroup$ Nov 17, 2018 at 18:47