This is the archived website of IC 312 from the Fall 2015 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Homework 2: Understanding Big-O

  • Due before class on Wednesday, September 2

For each of the following snippets of code, what is the Big-O of the worst case for that algorithm?

  1. 1
2
3
4

    int sum = 0;
for (int i = 0; i < n; i++) {
  sum++;
}
  2. 1
2
3
4

    int sum = 0;
for (int i = 0; i < n*n; i++) {
  sum++;
}
  3. 1
2
3
4
5
6

    int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
    sum++;
  }
}
  4. 1
2
3
4
5
6

    int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < i; j++) {
    sum++;
  }
}
  5. 1
2
3
4
5
6

    int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = 5; j < n; j++) {
    sum++;
  }
}
  6. 1
2
3
4
5
6

    int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = 1; j < n; j*=2) {
    sum++;
  }
}
  7. 1
2
3
4
5
6

    int sum = 0;
for (int i = 1; i < n; i*=2) {
  for (int j = 1; j < n; j++) {
    sum++;
  }
}
  8. 1
2
3
4
5
6
7
8

    int sum = 0;
for (int i = 1; i < n; i*=2) {
  for (int j = 1; j < n*n; j++) {
    for (int k = 0; k < j; k++) {
      sum++;
    }
  }
}