Classification of algorithms common mistakes

Common mistakes

• Assuming fewer lines means greater efficiency

  Concluding that an algorithm is more efficient simply because its code is shorter.

  Fix itCompare how the algorithm's time and space requirements change relative to the problem size. Code length alone does not establish efficiency.

• Confusing exponential and polynomial functions

  Treating y = 2x² and y = 2ˣ as the same type because both contain a 2 and an x.

  Fix itIn y = 2x², x is raised to a power, so it is polynomial. In y = 2ˣ, x is the exponent, so it is exponential.

• Counting exact operations instead of growth

  Giving an exact operation count, or retaining constants and lower-order terms, as the final Big-O answer.

  Fix itIdentify how the dominant part of the algorithm grows with n, then ignore constant factors and less significant terms when stating the Big-O classification.

• Confusing impractical with impossible

  Claiming that a computation has no possible solution simply because it cannot be completed on a particular computer.

  Fix itState that the computation may be impractical with the current algorithm, input size, time constraint, or hardware. Do not conclude that the problem is impossible without sufficient justification.

• Confusing intractable with impossible

  Assuming that an intractable problem cannot be solved at all.

  Fix itState that an intractable problem has no polynomial (or less) time solution. Do not state that it has no solution of any kind.

• Confusing difficulty with non-computability

  Assuming that a problem is non-computable simply because it is difficult, takes a long time, or has not yet been solved.

  Fix itNon-computability means that no algorithm can solve the problem in every case. Difficulty or lack of current progress alone does not establish this.

• Confusing halting with slow execution

  Stating that the Halting problem asks how long a program takes to finish.

  Fix itState that it asks whether the program will eventually stop at all, not how quickly it will stop.