# Analysis of Algorithms

## count

• Let’s consider this code so that we can provide an example for the asymptotic notation.

int count = 0;
for (int i = 0; i < N; ++i) {
if (arr[i] == 0) {
++count;
}
}

Let’s analyze this code and count how any operations it invokes. There is one assignment (count) before the for loop, plus another one inside (i). The for loop does $N + 1$ comparisons and $N$ updates (so $3 + 2N$ steps so far). On each iteration of the for loop (which executes $N$, we do one comparison and zero or one increments of count. So the total number of operations $R(N)$ is $3 + 3N \leq R(N) \leq 3 + 4N$. We can say that the execution time grows in the order of $N$, so the best way to describe the performance of the above snippet of code would be $\Theta(N)$. (It is also $O(N)$ and $\Omega(N)$.)

## hasDuplicates

• Now let’s consider this function.

bool hasDuplicates(const int numbers[], int size) {
for (int i = 0; i < size; i += 1) {
for (int j = 0; j < size; j += 1) {
if (numbers[i] == numbers[j]) {
return true;
}
}
}
return false;
}

What is the order of growth $R(N)$, where $N$ is the size of numbers array?

1. $R(N) \in \Theta(1)$.

2. $R(N) \in \Theta(N)$.

3. $R(N) \in \Theta(N^2)$.

4. Something else.

The correct answer is A. $R(N) \in \Theta(1)$. Notice that the very first comparison is numbers[i] == numbers[j] where i and j are both zero. It is always the case that numbers[0] == numbers[0], so the function always returns true in constant time. Notice that even though there are two for loops, the order of growth is $\Theta(1)$ and not $\Theta(N^2)$.

• Let’s fix the bug in hasDuplicates by changing j = 0 to j = i + 1.

bool hasDuplicates(const int numbers[], int size) {
for (int i = 0; i < size; i += 1) {
for (int j = i + 1; j < size; j += 1) {
if (numbers[i] == numbers[j]) {
return true;
}
}
}
return false;
}

Now, what is the order of growth $R(N)$, where $N$ is the size of numbers array?

1. $R(N) \in \Theta(1)$.

2. $R(N) \in \Theta(N)$.

3. $R(N) \in \Theta(N^2)$.

4. Something else.

The correct answer is D. Something else. It might seem that now that we’ve fixed the bug $R(N) \in \Theta(N^2)$. But that is only the case when we have to go through the entire array. For some arrays (e.g. an array of all zeros), we only have to compare the first two elements. So if the array contains just zeros, the function will execute in constant time regardless of the size of the array. Since the answer options have Big Theta and not Big O, the answer is something else (depends on the input). It is true, however, that $R(N) \in O(N^2)$.

## printHello

• Let’s try to analyze the time complexity of printHello. Find a simple function $f(n)$ such that the runtime $R(N) \in \Theta \left( f \left( n \right) \right)$. By simple, we mean that there should be no unnecessary multiplicative constants or additive terms.

void printHello(int n) {
for (int i = 1; i <= n; i *= 2) {
for (int j = 0; j < i; j += 1) {
cout << "hello" << endl;
}
}
}

What is $f \left( N \right)$?

1. $1$.

2. $\log N$.

3. $N$.

4. $N \log N$.

5. $N^2$.

6. Something else.

• As a hint, consider this image, where each blue square represents a print statement.

Notice how the outer for loop starts executing with i = 1, so we print "hello" one time one the first iteration (the inner for loop starts with j = 0 and executes so long as j < 1). On the second iteration of the outer loop, i is 2 and the inner for loop executes two times. On the third iteration of the outer loop, i is 4 (since each time we multiply i by 2) and we print "hello" four times. So when n is 4 (or 5, 6 or 7) "hello" is printed 1 + 2 + 4 = 7 times.

Finally, consider this table that computes $R(N)$ for different values of $N$.

N R(N)

1

1

2

1 + 2 = 3

7

1 + 2 + 4 = 7

8

1 + 2 + 4 + 8 = 15

27

1 + 2 + 4 + 8 + 16 = 31

185

…​ + 64 + 128 = 255

715

…​ + 256 + 512 = 1023

1023

…​ + 256 + 512 = 1023

1024

…​ + 512 + 1024 = 2047

So we can see that $R \left( N \right)$ is always the next power of two minus one. Observe that for each $N$, $R \left( N \right) \leq 2N$. In fact, we can add a new column to the above table to demonstrate that.

N R(N) 2N

1

1

2

2

1 + 2 = 3

4

6

1 + 2 + 4 = 7

12

7

1 + 2 + 4 = 7

14

8

1 + 2 + 4 + 8 = 15

16

27

1 + 2 + 4 + 8 + 16 = 31

54

185

…​ + 64 + 128 = 255

370

715

…​ + 256 + 512 = 1023

1430

1023

…​ + 256 + 512 = 1023

1046

1024

…​ + 512 + 1024 = 2047

2048

From the above table we see that if $N$ is a power of two, $R \left( N \right)$ is $2N - 1$. For all other $N$, $R \left( N \right)$ is less than $2N - 1$. In general, $R \left( N \right)$ is the sum of all powers of two that are less than or equal to $N$. It turns out that this sum increases linearly, with a constant factor of 2. And so the correct answer is C. $N$.

• Now let’s consider another function, recursive.

int recursive(int n) {
if (n <= 1) {
return 1;
}
return recursive(n - 1) + recursive(n - 1);
}

Again, try to find a simple function $f(n)$ such that the runtime $R(N) \in \Theta \left( f \left( n \right) \right)$. What is $f \left( N \right)$?

1. $1$.

2. $\log N$.

3. $N$.

4. $N \log N$.

5. $N^2$.

6. $2^N$.

• First, realize that this is a recursive function that calls itself twice. So we can represent the growth of runtime of the above code with this tree (when the input n is 5).

Notice that each node has two children. Also notice that the height of the tree is $N$.

We’ll come up with a recurrence relation that will express the number of steps the code has to execute and will help us find the overall complexity of the code. To do that, we’ll count the number of calls to recursive ($T(N)$) for an input of size $N$.

$T(N) = 2 T \left( N - 1 \right) + 1$

We can expand this recurrence relation a few times until we find a pattern.

\begin{aligned} T(n) &= 2 T \left( N - 1 \right) + 1 \\ &= 2 \left( 2 T \left( N - 2 \right) + 1 \right) + 1 \\ &= 2 \left( 2 \left( 2 T \left( N - 3 \right) + 1 \right) + 1 \right) + 1 \\ &= 2 \left( 2 \left( \cdots 2 \cdot 1 + 1 \right) + 1 \right) + \cdots 1 \\ &= 2 \left( \left( \cdots 2 \right) \cdot 1 + 1 \right) + \cdots 1 \\ &= 2^{N - 1} + 2^{N - 2} + \cdots + 1 = 2^N - 1 = \Theta \left( 2^N \right) \\ \end{aligned}

The intuition to solving this is that there are $N - 1$ 2s in the expanded version. (There are $N$ levels in the above binary tree and each node expcept the leaves has two children.)

To confirm, we can count the number of nodes on each level in the above tree.

Therefore, the correct answer is F. $2^N$.