This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
For each of the following snippets of code, what is the Big-O of the worst case for that algorithm?
1 2 | for (int i = 0; i < n; i++) sum++; |
1 2 | for (int i = 0; i < n*n; i++) sum++; |
1 2 3 | for (int i = 0; i < n; i++) for (int j = i; j < n; j++) sum++; |
1 2 3 | for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) sum++; |
1 2 3 | for (int i = 0; i < n; i++) for (int j = 5; j < n; j++) sum++; |
1 2 3 | for (int i = 0; i < n; i++) for (int j = 1; j < n; j*=2) sum++; |
1 2 3 | for (int i = 1; i < n; i*=2) for (int j = 1; j < n; j++) sum++; |
1 2 3 4 | for (int i = 1; i < n; i*=2) for (int j = 1; j < n*n; j++) for (int k = 0; k < j; k++) sum++; |