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

Let’s consider this code so that we can provide an example for the asymptotic notation.
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 ofcount
. 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?
$R(N) \in \Theta(1)$.

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

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

Something else.
The correct answer is A. $R(N) \in \Theta(1)$. Notice that the very first comparison is
numbers[i] == numbers[j]
wherei
andj
are both zero. It is always the case thatnumbers[0] == numbers[0]
, so the function always returnstrue
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 changingj = 0
toj = 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?
$R(N) \in \Theta(1)$.

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

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

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$.

$\log N$.

$N$.

$N \log N$.

$N^2$.

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 withj = 0
and executes so long asj < 1
). On the second iteration of the outer loop,i
is2
and the inner for loop executes two times. On the third iteration of the outer loop,i
is4
(since each time we multiplyi
by2
) and we print"hello"
four times. So whenn
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$.

$\log N$.

$N$.

$N \log N$.

$N^2$.

$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$.