What is the worst-case time complexity?

Answer: O(n) Linear search may inspect every element, giving O(n) worst case.

AP Computer Science A · Topic 7.5

Searching Practice

Part of ArrayList.

Practice questions

Want a predicted score for the whole AP CSA exam? Take the 20-question diagnostic and Lumi will plan the rest.

Take diagnosticarrow_forward Practice all 7.5

Sample questions

5 of 11 — sign in to practice the rest with adaptive difficulty and mastery tracking.

Sample 1difficulty 2/5

ArrayList<String> list = new ArrayList<>();
list.add("cat");
list.add("dog");
list.add("bird");
boolean found = false;
for (String s : list) {
    if (s.equals("dog")) found = true;
}
System.out.println(found);

What is printed?

A
$true$
check_circle
B
$false$
C
$dog$
D
$1$

Why

"dog" is in the list, so the if statement sets found to true.

View full solution & statsarrow_forward

Sample 2difficulty 2/5
```
int[] a = {2, 5, 2, 7, 2, 8};
int count = 0;
for (int x : a) {
  if (x == 2) count++;
}
```
$What is count?$
- A
  $4$
- B
  $2$
- C
  $3$
  check_circle
- D
  $1$
Why
$The value 2 appears at indices 0, 2, and 4, so count is 3.$
View full solution & statsarrow_forward
Sample 3difficulty 2/5
```
// linear search on array of size n
```
$What is the worst-case time complexity?$
- A
  $O(n^2)$
- B
  $O(log n)$
- C
  $O(n)$
  check_circle
- D
  $O(1)$
Why
$Linear search may inspect every element, giving O(n) worst case.$
View full solution & statsarrow_forward
Sample 4difficulty 2/5
```
int[] a = {3, 7, 1, 9, 4};
int target = 100;
int idx = -1;
for (int i = 0; i < a.length; i++) {
  if (a[i] == target) { idx = i; break; }
}
```
$What is idx after the loop?$
- A
  $-1$
  check_circle
- B
  $4$
- C
  $5$
- D
  $0$
Why
$Target 100 is not in the array, so idx remains its initial value of -1.$
View full solution & statsarrow_forward
Sample 5difficulty 2/5
```
int[] a = {1, 2, 3, 4};
int target = 99;
int idx = -1;
for (int i = 0; i < a.length; i++) {
  if (a[i] == target) {
    idx = i;
  }
}
System.out.println(idx);
```
$What is printed?$
- A
  $-1$
  check_circle
- B
  $4$
- C
  $0$
- D
  $ArrayIndexOutOfBoundsException$
Why
$99 is not in the array, so idx remains its initial value of -1. The convention -1 indicates "not found".$
View full solution & statsarrow_forward

Predict my AP scorearrow_forward