Asymptotic Analysis

Instant Noodles (su17-mt1-4)

For each of the functions below, find the order of growth that best describes the execution time as a function of N, the size of the input number n, or infinite if the function never terminates.

1. Code:

   def foo(n):
     i = 1
     while i < n:
       i += 10
     n += 5

2. Code:

   def baz(n):
     i = 1
     while i < n:
       j = i
       while j < n:
         while j < n:
           j += 1
         j += 1
       i += 1

3. Code:

   def bar(n):
     i = 1
     while i < n:
       i += i
     i += i

4. Code:

   def garply(n):
     for i in range(n):
       for j in range(n):
         for k in range(i + j):
           return garply(n - 1)

Will Code for Points (sp15-mt2-3)

1. Implement objectify, which takes a tree data abstraction and returns an equivalent Tree instance.

   class Tree:
   
     def __init__(self, root, branches=[]):
       self.root = root
       for branch in branches:
         assert isinstance(branch, Tree)
       self.branches = list(branches)
   
     def is_leaf(self):
       return not self.branches

   def objectify(t):
     """
     Return a Tree instance equivalent to a tree represented as a list.
   
     >>> m = tree(2)
     >>> m[2]
     >>> objectify(m)
     Tree(2)
     >>> r = tree(3, [tree(4, [tree(5), tree(6)]), tree(7, [tree(8)])])
     >>> r
     [3, [4, [5], [6]], [7, [8]]]
     >>> objectify(r)
     Tree(3, [Tree(4, [Tree(5), Tree(6)]), Tree(7, [Tree(8)])])
     """
   
     return 

2. What's the big-theta expression that describes the number of Tree instances constructed by calling obejctify on a tree with n nodes?