CSC236 Data Structures - Problem Set: Complexity

Problem Set: Complexity

Express the following running times in big O:
1. 10n
2. 10n + 2n²
3. 6
4. 5n² + n
5. n² + 5n
6. logn + 5n + 3
7. n + 2nlogn
8. n * (n - 1)) / 2
9. 2n² + 5nlogn + 1

Consider the following pseudocode:
```
   count = 0;
   for (i = 1 ; i <= N ; i++)
      count++;
   System.out.println(count);
```
1. In the worst case, how many times is each statement executed?
2. In the best case, how many times is each statement executed?
3. What is the total number of statements executed in the worst case?
4. What is the total number of statements executed in the best case?
5. What is the big O in the worst case?
6. What is the big O in the best case?

Consider the following pseudocode:
```
   count = 0;
   for (i = 0 ; i < 10 ; i++)
      count++;
   System.out.println(count);
```
1. In the worst case, how many times is each statement executed?
2. In the best case, how many times is each statement executed?
3. What is the total number of statements executed in the worst case?
4. What is the total number of statements executed in the best case?
5. What is the big O in the worst case?
6. What is the big O in the best case?

Consider the following pseudocode:
```
   count = 0;
   amount = 0;
   for (i = 1 ; i <= N ; i++)
      count++;
   System.out.println(count);
   for (i = 1 ; i < N ; i++)
      arr[i] += count;
```
1. In the worst case, how many times is each statement executed?
2. In the best case, how many times is each statement executed?
3. What is the total number of statements executed in the worst case?
4. What is the total number of statements executed in the best case?
5. What is the big O in the worst case?
6. What is the big O in the best case?

Consider the following pseudocode:
```
   num = 1;
   amount = N;
   amount = amount + N * (N - 1);
   num = num + amount;
```
1. In the worst case, how many times is each statement executed?
2. In the best case, how many times is each statement executed?
3. What is the total number of statements executed in the worst case?
4. What is the total number of statements executed in the best case?
5. What is the big O in the worst case?
6. What is the big O in the best case?

Consider the following pseudocode:
```
   tot = 0
   for (i = 0 ; i < n ; i++) {
      C[i] = A[i] + B[i]
      if (A[i] > B[i])
         tot = tot + A[i]
   }
```
1. In the worst case, how many times is each statement executed?
2. In the best case, how many times is each statement executed?
3. What is the total number of statements executed and what is the big O in the worst case?
4. What is the total number of statements executed and what is the big O in the best case?
5. Sometimes we want to focus on certain operations, and ignore "bookkeeping" operations like testing loop conditions and incrementing subscripts. For example, we might want to count the number of times we use an array. In that case we count array references: any time we use an array in an assignment statement or a condition. We count each time we use an array, even if we use it more than once in a statement. Count the total number of references to array elements in the worst case. Using the count of array references, what is the big O complexity of this algorithm in the worst case?

Consider the following pseudocode:
```
   tot = 0
   if ((A[0] == B[0])
      for (i = 1 ; i < n ; i++) {
         C[i] = A[i] + B[i]
         tot = tot + A[i]
   }
```
1. In the worst case, how many times is each statement executed?
2. In the best case, how many times is each statement executed?
3. What is the total number of statements executed and what is the big O in the worst case?
4. What is the total number of statements executed and what is the big O in the best case?
5. Sometimes we want to focus on certain operations, and ignore "bookkeeping" operations like testing loop conditions and incrementing subscripts. For example, we might want to count the number of times we use an array. In that case we count array references: any time we use an array in an assignment statement or a condition. We count each time we use an array, even if we use it more than once in a statement. Count the total number of references to array elements in the worst case. Using the count of array references, what is the big O complexity of this algorithm in the worst case?

Consider the following pseudocode:
```
   count = 0;
   for (i = 1 ; i <= N ; i++) {
      count++;
      for (k = 1 ; k <= N/4 ; k++)
         arr[k] += count;
   }
   System.out.println(count);
```
1. In the worst case, how many times is each statement executed?
2. In the best case, how many times is each statement executed?
3. What is the total number of statements executed in the worst case?
4. What is the total number of statements executed in the best case?
5. What is the big O in the worst case?
6. What is the big O in the best case?

Consider the following pseudocode:
```
   tot = 0;
   for (i = 0 ; i < n ; i++) {
      for (j = 0 ; j < m ; j++) {
         if (arr[i][j] > 0) {
            tot = tot + arr[i][j];
            arr[i][j] = 0;
         }
      }
   }
```
1. In the worst case, how many times is each statement executed?
2. Count the total number of references to array elements in the worst case. If the operation we are counting is array references, what is the big O complexity of this algorithm in the worst case?
3. Count the total number of references to array elements in the best case. If the operation we are counting is array references, what is the big O complexity of this algorithm in the best case?

Consider the following pseudocode:
```
   count = 0;
   for (int i = 0 ; i < N ; i++)
      for (int j = 0 ; j < N ; j++)
         if (a[i] + a[j] + a[k] == 0)
            for (int k = 0 ; k < N ; k++)
               count++;
```
1. In the worst case, how many times is each statement executed?
2. What is the big O complexity in the worst case?
3. In the best case, how many times is each statement executed?
4. What is the big O complexity in the best case?

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2019