# Big-O Exercises

## Exercises

### 1

This code computes the product of two variables, what is the runtime of this code?

```
int product(int a, int b) {
int sum = 0;
for (int I = 0; I < b; I++) {
sum += a;
}
return sum;
}
```

### 2

This code computes A ^ B, what would be the runtime?

```
static int power(int a, int b) {
if (b < 0) return a;
if (b == 0) return 1;
int sum = a;
for (int I = 0; I < b - 1; I++) {
sum *= a;
}
return sum;
}
```

### 3

This code computes A% B, what would be the runtime?

```
int mod(int a, int b) {
if (b <=a) return -1;
int div = a / b;
return a - div * b;
}
```

### 4

This code computes a division between whole integers (assuming both are positive), what would be the runtime?

```
int div(int a, int b) {
int count = a;
int sum = b;
while (sum <= a) {
sum += b;
count++;
}
return count;
}
```

### 5

The following code calculates the square root of an integer. If the number is not a perfect square (there is no whole square root), then return -1. If N is 100, first guess if N is 50. Too high? Try something lower, halfway between 1 and 50, etc. What is the big-o?

```
int sqrt(int n) {
return sqrt_helper(n, 1, n);
}
int sqrt_helper(int n, int min, int max) {
if (max < min) return -1;
int guess = (min + max) / 2;
if (guess * guess == n) {
return guess;
} else if (guess *guess <n) {
return sqrt_helper(n, guess + 1, max) ;
} else {
return sqrt_helper(n, min, guess - 1);
}
}
```

### 6

The following code calculates the square root of an integer. If the number is not a perfect square (there is no whole square root), then return -1. It does so by trying larger and larger numbers until it finds the correct value (or is too high). What is your runtime?

```
int sqrt(int n) {
for (int guess = 1; guess * guess < n; guess++) {
if (guess * guess == n) return guess;
}
return -1;
}
```

### 7

If a binary search tree (BST) is not balanced, how long could it take in the worst case to find an item?

### 8

What would be the worst case if we are looking for a value in a binary tree (Binary Tree - BT) that is not ordered?

### 9

The appendToNew method adds a value to an array by creating a new, longer array and returning this longer array. How long does it take to copy the array?

```
int[] copyArray(int[] array) {
int[] copy = new int[0];
for (int value : array) {
copy = appendToNew(copy, value);
}
return copy;
}
int[] appendToNew(int[] array, int value) {
int[] bigger = new int[array.length + 1];
for (int I = 0; I < array. length; I++) {
bigger[I] = array[I];
}
bigger[bigger.length - 1] = value;
return bigger;
}
```

### 10

The following code adds the digits of a number. What is your runtime?

```
int sumDigits(int n) {
int sum = 0;
while (n > e) {
sum += n % 10;
n /= 10;
}
return sum;
}
```

### 11

The following code calculates the intersection (the number of elements in common) of two Arrays. Assuming that no Array has duplicates. Calculate the big-O notation of the intersection function which is ordering Array B and then iterating through Array A - making a check (Binary Search) if each value is in B. What is its execution time?

```
int intersection(int[] a, int[] b) {
mergesort(b);
int intersect =0;
for (int x : a) {
if (binarySearch(b, x) >= 0) {
intersect++;
}
}
return intersect;
}
```

## Answers

- O(B) It would be Linear runtime on B, since the loop only iterates on B.
- O(B) It would be Linear runtime on B, since the loop only iterates on B.
- O(1) Constant Runtime
- O(A / B) The count variable will eventually be A / B. The While loop will eventually iterate the same as A / B.
- O(Log N) This algorithm is essentially doing a binary search to find the square root.
- O(Square Root(N)). This is a simple loop that for when we find guess * guess > N. In other words guess > sqrt (N).
- O(N), where N is the number of leaves in the tree. The maximum possible time would be the depth of the tree.
- O(N), without any order - we would have to look all the nodes in the tree.
- O(N ^ 2) where N is the number of elements in the array.
- O(Log N) The runtime would be the number of digits in the number.
- O(B log B + A log B), First we have to order the Array B - which entails B Log B. Then for each element in Array A - we will do a binary search in Log B, which would remain as A Log B.