This is the archived website of SY 301 from the Fall 2016 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 Tuesday, September 6

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

  1. 1
2
3

    sum = 0;
for i in range(n):
    sum += 1
  2. 1
2
3
4
5
6

    sum = 0;
i = 0
while i < n*n:
    sum += 1
    i += 1
}
  3. 1
2
3
4
5
6

    sum = 0;
for i in range(n):
    j = i
    while j < n:
        sum += 1
        j += 1
  4. 1
2
3
4

    sum = 0;
for i in range(n):
    for j in range(i):
        sum += 1
  5. 1
2
3
4
5
6

    sum = 0;
for i in range(n):
    j = 5
    while j < n:
        sum += 1
        j += 1
  6. 1
2
3
4
5
6
7
8

    sum = 0;
i = 0
while i < n:
    j = 1
    while j < n:
        sum += 1
        j *= 2
    i += 1
  7. 1
2
3
4
5
6
7
8

    int sum = 0;
i = 1
while i < n:
    j = 1
    while j < n:
        sum += 1
        j += 1
    i *= 2
  8. 1
2
3
4
5
6
7
8
9
10
11

    sum = 0;
i = 1
while i < n:
    j = 1
    while j < n*n:
        k = 0
        while k < j:
            sum += 1
            k += 1
        j += 1
    i *= 2