Homework 2: Understanding Big-O

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. 1
    2
    
    for (int i = 0; i < n; i++)
        sum++;
  2. 1
    2
    
    for (int i = 0; i < n*n; i++)
        sum++;
  3. 1
    2
    3
    
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
          sum++;
  4. 1
    2
    3
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
          sum++;
  5. 1
    2
    3
    
    for (int i = 0; i < n; i++)
        for (int j = 5; j < n; j++)
          sum++;
  6. 1
    2
    3
    
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j*=2)
          sum++;
  7. 1
    2
    3
    
    for (int i = 1; i < n; i*=2)
        for (int j = 1; j < n; j++)
          sum++;
  8. 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++;