Skip to main content

Welcome to Programming and Data Structures

Andrew Scholer

Exercises 25.15 Exercises

1.

Give the Big-O notation for the following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
void foo(int n) {
  for (int i = 0; i < n - 5; i++) {
    cout << i << endl;
  }
}
🔗

2.

Give the Big-O notation for the following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
void foo(int n) {
  for (int i = 0; i < n; i += 2) {
    cout << i << endl;
  }

  cout << "----" << endl;

  for (int j = 0; j < n / 2; j++) {
    cout << j << endl;
  }

  cout << "----" << endl;
}
🔗

3.

Give the Big-O notation for the following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
void foo(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      cout << i << ", " << j << endl;
    }
  }
}
🔗

4.

Give the Big-O notation for the following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
void foo(int n) {
  cout << "----" << endl;
  for (int i = 0; i < 5; i++) {
    for (int j = i; j < n; j *= 2) {
      cout << i << ", " << j << endl;
    }
  }
  cout << "----" << endl;
  int k = n;
  while (k > 0) {
    cout << k << endl;
    k--;
  }
  cout << "----" << endl;
}
🔗

5.

Give the Big-O notation for the following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
Assume bar is known to run in \(O(n)\) time.
🔗
void foo(int n) {
  cout << "----" << endl;
  bar(n);
  bar(n / 2);
  cout << "----" << endl;
}
🔗

6.

Give the Big-O notation for the following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
Assume bar is known to run in \(O(n)\) time.
🔗
void foo(int n) {
  cout << "----" << endl;
  for (int i = 0; i < n * 2; i++) {
    bar(i);
  }
  cout << "----" << endl;
}
🔗

7.

Give the Big-O notation for foo following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
void bar(int n) {
  cout << n << endl;
}

void foo(int n) {
  cout << "----" << endl;
  for (int i = 0; i < 100; i++) {
    bar(i);
  }
  cout << "----" << endl;
}
🔗

8.

Give the Big-O notation for foo following function. Explain your reasoning. Make sure to describe how each loop and function call contributes to the overall complexity.
🔗
void bar(int n) {
  for(int i = 0; i < n; i++) {
    cout << "*";
  }
}

void foo(int n) {
  cout << "----" << endl;
  for (int i = 0; i < n; i++) {
    bar(2 * n);
  }
  cout << "----" << endl;
}
🔗
You have attempted of activities on this page.
🔗
PrevTopNext