I need help for the order of growth for functions in Python 3.

Q1: What is the order of growth for the following functions?

Kinds of Growth

Here are some common orders of growth, ranked from no growth to fastest growth:

1. (1) constant time takes the same amount of time regardless of input size

2. (log n) logarithmic time

3. (n) linear time

4. (n log n) linearithmic time

5. (n² )

6. (n³ ), etc. polynomial time

7. (2ⁿ), (3ⁿ), etc. exponential time (considered intractable; these are really, really horrible)

8. Something else not listed

You should create a parameter-free function called question1 and return a list with 10 numbers. You should put the corresponding growth rate (1-8) for each of the problems listed below.

For example:

Answer: 3 (that is linear time)

Explanation (you do not have write it but you will in the exam, so make sure you understand your choice):

There is a single loop that runs n5 times. Each time the loop runs it executes 1 instruction in the loop header and 1 instruction in the body of the loop. The total number of instructions is 2 (n 5) + 1 (for the last loop check) = 2n 9 = (n)

If you need more examples, you can look here: https://www.comp.nus.edu.sg/~cs1020/tut/15s2/tut09ans/T9_ans.pdf

Please note:

1) They use big-O notation, which is the same as big-Theta for our purposes. (Big-O is an upper bound and Big-Theta is a tight bound, but in computer science both bounds are often used interchangeably.)

2) They use Java syntax in their loops. You can read it as:

for (int i = 0; i < n; i=i+1)

a) i is initialized to a 0.

b) if i is less than n, perform one iteration of the loop

c) increment i by 1, check if i is less than n. If it is, run the loop again etc; if i is greater than n, stop.

Equivalent loop in Python is: for i in range(0, n)

Question 1.1

def foo(n): i = 1 sum = 0 while i <= 20**20: sum = sum + i i = i * 2 return sum

Question 1.2

def func(n): sum = 0 for i in range(n): sum = sum + n for j in range(n * n * n): sum = sum + 10 return sum

Question 1.3

def func(n): j = 1 sum = 100 while j <= n: for i in range(1, n//2): sum = sum + i*j j = j + 1 return sum

Question 1.4

def func(n): sum = 111 for i in range(1, n+2): for j in range(i): sum = i + j return sum

Question 1.5

def func(n): i = 1 sum = 0 while i <= n: sum = sum * i i = i * 5 return sum

Question 1.6

def mod_10(n): if n % 10 == 0: return 10 else: return 1 + mod_10(n-1)

Question 1.7

Calculate the complexity for foo(bar(n)). To see pattern I'd suggest you to take different inputs for n and write down the recursion tree.

def bar(n): if n%2 == 1: return n + 1 return n def foo(n): if n < 1: return 2 if n % 2 == 0: return foo(n-1) + foo(n-2) else: return 1 + foo(n-2)

Question 1.8

def func(alist): for num in range(len(alist)-1,0,-1): for i in range(num): if alist[i] > alist[i+1]: alist[i], alist[i+1] = alist[i+1], alist[i]

Question 1.9

def func(n): for i in range(0,n): for j in range (i+1, i, -1): for k in range(n, j, -1): print("print")

Question 1.10

Calculate the complexity for second(n).

def first(n): for i in range(0, n): print("one") def second(n): for i in range(0, n): first(n)