<a href="https://colab.research.google.com/github/hannahcodes111/fp1/blob/main/Copy_of_BigO_and_Recurrence_Relationship.ipynb" target="_parent"></a>


1. List following function in incresing order in term of its growth (Big O notation). Don't forget to put its Big O beside each function
 $n!$, $\log_2 n $, $n - n^3 + 7n^5$, $n^2$, $2^n$, $10$, $(\log_2{n})^2$, $\frac{1}{n}$, $(\frac{1}{3})^n$, $\sqrt{n}, n^{\frac{1}{3}}-\log_2{n}$, $n^{log_2{n}}$


**Answer:**

2. Solve the following recurrence exactly:
\begin{equation}
  T(n)=\begin{cases}
    8, & \text{if $n=1$}.\\
    3T(n-1), & \text{$n \ge 2$}.
  \end{cases}
\end{equation}

**Answer:**

3. Solve the following recurrence exactly:
\begin{equation}
  T(n)=\begin{cases}
    4, & \text{if $n=1$}.\\
    2T(\frac{n}{2}) + 3n + 2, & \text{$n \ge 2$}.
  \end{cases}
\end{equation}

**Answer:**


4. Solve the following recurrence exactly:
\begin{equation}
  T(n)=\begin{cases}
    4, & \text{if $n=1$}.\\
    3T(\frac{n}{2}) + n^2 - 2n + 1, & \text{$n \ge 2$}.
  \end{cases}
\end{equation}

**Answer:**

5. Compare the two sorting algorithm below based on its running time (using `timeit`) with input from $n = 2$ to $10000$ with increment of $10$. Plot the result using matplotlib plot function.



```
# -*- coding: utf-8 -*-
"""
Bubble Sort
Created on Wed Feb  3 10:15:52 2021
@author: isandjaja
"""
import random
""

A = [random.randrange(2,10000,10) for i in range(10)]

print(A)

def bubblesort(A):
    n = len(A)
    for i in range(n):
        for j in range(n-1):
            print("i,j,j+1", i,j,j+1)
            if A[j] > A[j+1]:
                A[j],A[j+1] = A[j+1], A[j] #Swap A[j]
            print(A)
    return A
          
print("Sorted A")      
B = bubblesort(A)
print(B)
if __name__ == "__main__":  
  from timeit import timeit
  print(timeit(bubblesort(A), number=5))
  print(timeit(bubblesort(A), number=5))    
```


```
# -*- coding: utf-8 -*-
"""
MergeSort
Created on Fri Feb  5 10:43:30 2021
@author: isandjaja
"""
import random

A = [random.randrange(1,50,1) for i in range(10)]

print(A)

def merge(A,B):
    lenA = len(A)
    lenB = len(B)
    i = 0 # index for A
    j = 0 # index for B
    result = []
    print("Merge part (begin)",A,B)
    while(i<lenA) and (j<lenB):
        if A[i] <= B[j]:
            result.append(A[i])
            i += 1
        else:
            result.append(B[j])
            j += 1
    
    # Copy remaining elements to result        
    while(i<lenA):
        result.append(A[i])
        i += 1
    while(j<lenB):
        result.append(B[j])
        j += 1   
    print("Merge part (end)", result)
    return result

def mergesort(A):
    n = len(A)
    if n<=1:
        return A
    else:
        mid = n//2
        a = A[:mid]
        b = A[mid:]
        print("Divide part",a,b)
        return merge(mergesort(a),mergesort(b))

print("Sorted A")      
B = mergesort(A)
print(B)
```


```

```

d77ad26c0406a3127bf1f382c62c2ad212e3b11c
ipynb
Jupyter Notebook
Copy_of_BigO_and_Recurrence_Relationship.ipynb
hannahcodes111/fp1
88ee01d874f530ee8f3a451785d9f1e8c9bcbcf1
MIT
Copy_of_BigO_and_Recurrence_Relationship.ipynb
hannahcodes111/fp1
88ee01d874f530ee8f3a451785d9f1e8c9bcbcf1
MIT
Copy_of_BigO_and_Recurrence_Relationship.ipynb
hannahcodes111/fp1
88ee01d874f530ee8f3a451785d9f1e8c9bcbcf1
MIT
Qwen/Qwen-72B
1. YES
2. YES