# Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

## Section2.10Algorithm Analysis: Exercises

### ExercisesExercises

#### 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;
}
}


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