1.
Give the Big O performance of the following code fragment:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int k = i + j;
}
}
Section 2.10 Algorithm Analysis: Exercises
Exercises Exercises
2.
Give the Big O performance of the following code fragment:
for (int i = 0; i < n; i++) {
int k = 2 * i;
}
3.
Give the Big O performance of the following code fragment:
int i = n;
while (i > 0) {
int k = 2 * i;
i = i / 2;
}
4.
Give the Big O performance of the following code fragment:
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
result = i + j + k;
}
}
}
5.
Give the Big O performance of the following code fragment:
int result = 0;
for (int i = 0; i < n; i++) {
result = i + i;
}
for (int j = 0; j < n; j++) {
result = j + j;
}
for (int k = 0; k < n; k++) {
result = k + k;
}
6.
Devise an experiment to verify that the
ArrayList indexOf method is \(O(n)\text{.}\)
7.
Devise an experiment to verify that
get and put are \(O(1)\) for HashMaps.8.
Devise an experiment that compares the performance of the
remove method on ArrayLists and HashMaps.9.
Given a list of numbers in random order, write an algorithm that works in \(O(n\log(n))\) to find the \(k\text{th}\) smallest number in the list.
10.
Can you improve the algorithm from the previous problem to be linear? Explain.
You have attempted of activities on this page.
