Skip to content

Problems

Concepts

  1. What does time complexity mean?
  2. What is upper bound? Lower bound?
  3. What is the difference between O(1) and O(N)?
  4. Why is it important to consider worst-case when developing an algorithm?

Big O Exercises

Give the Big O of the following snippets of code

Example 1

1
2
3
4
5
6
7
8
int min = INT_MIN;
int max = INT_MAX;
for (int i = 0; i < n; i++) {
    if (arr[i] > max) max = arr[i];
}
for (int i = 0; i < n; i++) {
    if (arr[i] < min) min = arr[i];
}

Example 2

1
2
3
4
5
6
int min = INT_MIN;
int max = INT_MAX;
for (int i = 0; i < n; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
}

Example 3

1
2
3
4
5
6
7
8
9
void foo(int arr[], int size) {
    int sum = 0;
    int product = 1;
    for (int i = 0; i < size, i++)
        sum += arr[i];
    for (int i = 0; i < size; i++)
        product *= arr[i];
    cout << sum << ", " << product;
}

Example 4

1
2
3
4
5
void printPairs(int arr[], int size) {
    for (int i = 0; i < size, i++)
        for (int j = 0; j < size; j++)
            cout << arr[i] << " " << arr[j];
}

Example 5

1
2
3
4
5
void printUnorderedPairs(int arr[], int size) {
    for (int i = 0; i < size, i++)
        for (int j = i + 1; j < size; j++)
            cout << arr[i] << " " << arr[j];
}

Comments