If you need help reviewing Orders of Growth, take a look at these resources:

This link (from the Summer 2012 version of 61A) has some practice problems for orders of growth. Take a look!

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

## Conceptual Questions

### Question 1

Find the time complexity of `main`

in big-Theta (θ) notation.

```
def helper(x):
for i in range(x):
print(i)
return x
def main(n):
if n == 2:
return 0
else:
return helper(n - 1) + helper(n - 2)
```

θ(n)

### Question 2

Find the time complexity of `bar`

in big-Theta (θ) notation.

```
def foo(x):
for i in range(x):
for j in range(x):
print(x)
def bar(n):
while n > 0:
foo(100000)
n -= 1
```

θ(n)

### Question 3

Find the time complexity of `funny`

in big-Theta (θ) notation.

```
def joke(n):
for i in range(n**2):
print(i)
def funny(n):
for i in range(n**2):
print(joke(100))
return 'haha'
```

θ(n^{2})