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++;     }   } }