CS 385, Lab: Analysis of Algorithms
Name: Liam Brew Date: 02.07.2020
Pledge: I pledge my honor that I have abided by the Stevens Honor System. -Liam Brew
Give the complexity of the following functions. Choose the most appropriate notation from among 𝛰, θ,
and Ω.
1. void function1(int n) {
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += 2) {
cout << "*";
}
}
}
Answer: θ(n2)
2. void function2(int n) {
int count = 0;
for (int i = 1; i * i <= n; i++) {
count++;
}
cout << count;
}
Answer: θ(√n )
3. void function3(int n) {
int count = 0;
for (int i = n/2; i <= n; i++) {
for (int j = 1; j + n/2 <= n; j++) {
for (int k = 1; k <= n; k *= 2) {
count++;
}
}
}
cout << count;
}
Answer: θ(𝑛2 ∗ lg(𝑛))
4. void function4(int n) {
int count = 0;
for (int i = n/2; i <= n; i++) {
for (int j = 1; j <= n; j *= 2) {
for (int k = 1; k <= n; k *= 2) {
count++;
}
}
}
cout << count;
}
Answer: θ(n ∗ lg(n) ∗ lg(n))
CS 385, Lab: Analysis of Algorithms
5. void function5(int n) {
if (n % 2 == 0) {
return;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << "*";
break;
}
}
}
Answer: O(n)
6. void function6(int n) {
int count = 0;
for (int i = 1; i <= n/2; i++) {
for (int j = 1; j <= n/3; j++) {
for (int k = 1; k <= n/4; k++) {
count++;
}
}
}
cout << count;
}
Answer: θ(𝑛3 )
7. void function7(int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j += i) {
cout << "*";
}
}
}
Answer: θ(n ∗ log(n))
8. void function8(int n) {
int i = 1, s = 1;
while (s <= n) {
i++;
s += i;
cout << "*";
}
}
Answer: θ(√𝑛 )
9. Processing Arrays
a. Suppose you have an unsorted array of integers of length 𝑛 and want to sum all the
elements inside it. What is the running time of your algorithm? θ(n)
b. Suppose you have an unsorted array of integers of length 𝑛 and want to determine if all the
values inside are positive. What is the running time of your algorithm? O(n)
CS 385, Lab: Analysis of Algorithms
c. Suppose you have a sorted array of integers of length 𝑛 and want to determine the median
value. What is the running time of your algorithm? θ(1)
10. T T / F 𝑓 (𝑛) = 3𝑛2 + 4𝑛 + 2 ∈ θ(𝑛2 )
If true, prove it by giving integral values for the required constants 𝑐1 , 𝑐2 , and 𝑛0 . Choose the
tightest values possible for the 𝑐1 and 𝑐2 constants. If false, show the contradiction.
Upper Bound: 3n2 + 4n + 2 <= 3n2 + 5n for all n >= 1 → 3n2 + 5n <= 4n2 for all n >= 5 → c1 = 4
Lower Bound: 3n2 + 4n + 2 >= 3n2 for all n >= 1 → c2 = 3
Therefore no = max(n1, n2) = max(1, 5) = n0 = 5
