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