What is the complexity of a recursive snowflake function?

Question

# The base case basically draws a segment.

import turtle
def fractal(order,length):
    if order==0:
        turtle.forward(length)
    else:
        l=length/3
        fractal(order-1,l)
        turtle.left(60)
        fractal(order-1,l)
        turtle.right(120)
        fractal(order-1,l)
        turtle.left(60)
        fractal(order-1,l)
def snowflake(order,length):
    fractal(order,length)
    turtle.right(120)
    fractal(order,length)
    turtle.right(120)
    fractal(order,length)
snowflake(3,300)
turtle.speed(0)
turtle.done()

This is a recursive function that traces a fractal shaped snowflake. The complexity depends on order. However, I can't figure it out when we have so many recursive actions happening for every order.

Answer 1

Although the function might look complicated, it is worth noting that the execution of fractal only depends on order. So complexity-wise, it can be reduced to just:

def fractal(order):
    if order == 0:
         # do O(1)
    else:
        fractal(order - 1)
        fractal(order - 1)
        fractal(order - 1)

i.e. 3 recursive calls with order - 1; the time complexity recurrence is then very simple:

T(n) = 3 * T(n - 1) (+ O(1))
T(1) = O(1)

– which easily works out to be O(3^n).

snowflake has 3 identical calls to fractal, so is also O(3^n).