Terrible implementations of is_even

I stumbled on this written as a joke somewhere on the web and found it hilariously terrible. What a way to turn a O(1) modulus operation into the glorious abomination you see here.

def is_even(num):
  x = abs(num)
  # x is even if it can be divided into two parts y and z that equal each other
  y,z = 0,0
  # take turns incrementing y and z
  for i in range(x):
    if is_even(i):
      y += 1
    else:
      z += 1
  return (y == z)

  1. Runtime(x) = Runtime(x-1) + Runtime(x-2) + ... + Runtime(0)
  2. Runtime(x-1) = Runtime(x-2) + Runtime(x-3) + ... + Runtime(0)
  3. Runtime(x) = 2 * Runtime(x-1) = 2 * 2 * Runtime(x-2) = ... = 2 * 2 * 2 * ... * Runtime(0) = 2^x * const.

     This algorithm has a runtime of O(2n)

Leave a Reply

Your email address will not be published. Required fields are marked *