title: Koch snowflake rendering time (and how to draw a snowflake using turtle)
body: <p>I'm currently working through the online course material for the MIT 6.006 course for fun. I'm on problem set #2 (found <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/" rel="nofollow">here</a>) and had a question about the calculations for the asymptotic rendering time for the koch snowflake problem (problem #1). </p>
  
  <p>According to the solutions, when the CPU is responsible for the rendering and the calculation of coordinates, the asymptotic rendering time is faster than if the process is split up between the CPU and GPU. The math makes sense to me, but does anyone have an intuition about why this is true? </p>
  
  <p>In my mind, the CPU still has to calculate the coordinates to render the snowflake (Theta(4^n) time), and then has to render the image. In my mind, these should be additive, not multiplicative. </p>
  
  <p>However, the solutions state these are multiplicative, so since each triangle/line segment is shorter (for the last two subproblems in problem 1) the runtime is reduced to either Theta((4/3)^n) or Theta(1)!</p>
  
  <p>I'm not a computer scientist--this stuff is just a fun hobby for me. I'd really appreciate an answer from one of you geniuses out there :)</p>
  
  <p>Also, some fun I had while playing with the python turtle module. Heres some very imperfect code to draw a koch snowflake in python:</p>
  
  <pre><code>import turtle
  
  def snowflake(n,size=200):
      try: turtle.clear()
      except: pass
      turtle.tracer(0,0)
      snowflake_edge(n,size)
      turtle.right(120)
      snowflake_edge(n,size)
      turtle.right(120)
      snowflake_edge(n,size)
      turtle.update()
      turtle.hideturtle()
  
  def snowflake_edge(n,size=200):
      if n==0:
          turtle.forward(size)
      else:
          snowflake_edge(n-1,size/3.0)
          turtle.left(60)
          snowflake_edge(n-1,size/3.0)
          turtle.right(120)
          snowflake_edge(n-1,size/3.0)
          turtle.left(60)
          snowflake_edge(n-1,size/3.0)
  </code></pre>