### *Problem 1.*
What is the run-time complexity of each of the following algorithms:
>[!question]
>```cpp
>// Alg 1 (primarity check)
>for (i=2..sqrt(N)) {
> if ( N % i == 0 ) return false;
>}
>return true;
>```
>>[!check] $O(\sqrt{ N })$
>[!question]
>```cpp
>// Alg 2 (primarity check)
>for (i=1..100) {
> if ( N % rand() == 0 ) return false;
>}
>return true;
>```
>>[!check] O(1)
>[!question]
>```cpp
>// Alg 3
>C=N
>for (i=1..N) {
> for (j=1..C) { // C defined above
> print "."
> }
> C /= 2;
>}
>```
>>[!check] $O(N)$
>[!tip] Brute force 'testing'
>```python
>from math import *;
>
>def q3(N: int) -> int:
> C = N
> count = 0
> for i in range(1, N+1):
> for j in range(1, floor(C)+1 ):
> count += 1
> C /= 2
> return count
>
>def O(N: float)-> float:
> return 2*N
>
>def p(N: int):
> print(f"f({N}) -> {q3(N)}, expected: {O(N)}, error = {q3(N) - O(N)}")
>
>p(10)
>p(42)
>p(100)
>p(221)
>p(532)
>p(13201)
>p(50010)
>p(51010)
>```
>[!question]
>```cpp
>Alg 4 (one line change from above)
>C=N
>for (i=1..N) {
> for (j=1..C) { // C defined above
> print "."
> }
> C -= 2; // this line was changed
>}
>```
>>[!check]
>[!tip] Brute force 'testing'
```python
from math import *;
def q3(N: int) -> int:
C = N
count = 0
for i in range(1, N+1):
for j in range(1, C+1 ):
count += 1
C -= 2
return count
def O(N: float)-> float:
return N*N
def p(N: int):
print(f"f({N}) -> {q3(N)}, expected: {O(N)}, error = {q3(N) - O(N)}")
p(10)
p(30)
p(50)
p(60)
p(80)
```
### Problem 2.
For this problem we will consider operation *merge* and
- implement and
- analyze it
for several data structures as we need in `DS-runtimes.html`
The idea of the operation:
- You have 2 objects of the same data structure (say sorted array).
- You want to create an object of the same type, which includes elements of both. The 2 original objects may be reused, i.e. the original objects will never be used again.
#### ***Subproblem sorted array.***
Assume the same size N.
Suboptimal solution:
create array to store the result - $O(1)$
copy both array $O(N) + O(N)$
sort result $O(2N\log_{2}N)=O(N\log N)$
Total = $O(N\log N)$
Optimal solution:
- Assume the same size N.
- Create array to store the result - $O(1)$
- Use 2-ptr traversal: $O(2N)$
- Start in the beginning of each array
- compare elements copy smaller to result
- Increment index in whichever array contained the smaller element
- continue till one of the indices hits the end
- copy the remainder of the other array
Total = $O(N)$
```python
def merge(list1: [float], list2: [float]):
output: [float] = []
assert(len(list1)== len(list2))
j = 0
k = 0
for i in range(len(list1) * 2):
if j == len(list1):
output.append(list2[k])
k += 1
continue
elif k == len(list1):
output.append(list1[j])
j += 1
continue
a = list1[j]
b = list2[k]
if a < b:
j = j + 1
output.append(a)
else:
k = k + 1
output.append(b)
return output
print(merge(
([1, 4, 5, 6, 42]),
([2, 3, 7, 8, 13])
))
```
Note: what if one of the arrays has enough unused element to contain the other array (we are allowed to "break" the arguments)? We will get a suboptimal solution like above.
***Subproblem unsorted array.***
***Subproblem unsorted list.***
***Subproblem sorted list.***
***Subproblem balanced BST.***