IC 312 Fall 2022 / HWs

This is the archived website of IC 312 from the Fall 2022 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Homework 02: Big-O of Loops

Name: _____________________________________________ Alpha: ___________________

Describe help received: ________________________________________________________

Print this page
  • Due before class on Friday, September 2
  • This is a written homework - be sure to turn in a hard-copy of your completed assignment at the beginning of class on the deadline.

For each of the program-snippets below, what is the big-O of the operation? Show all of your work and clearly indicate your final answer.

  1.  

    int sum = 0;
for (int i = 0; i < n; i++) {
    sum++;
}


  1.  

    int sum = 0;
for (int i = 0; i < n*n; i++) {
    sum++;
}


  2.  

    int sum = 0;
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
       sum++;
    }
}


  3.  

    int sum = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        sum++;
    }
}


  4.  

    int sum = 0;
for (int i = -5; i < n; i++) {
    for (int j = -5; j < n; j++) {
        sum++;
    }
}


  5.  

    int sum = 0;
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j*=2) {
        sum++;
    }
}


  6.  

    int sum = 0;
for (int i = 1; i < n; i*=2) {
    for (int j = 1; j < n; j++) {
        sum++;
    }
}


  7.  

    int sum = 0;
for (int i = 1; i < n; i++) {
    for (int j = 0; j < n*i; j++) {
        sum++;
    }
}


  8.  

    int sum = 0;
for (int i = 1; i < n; i++) {
    for (int j = 0; j < i/2; j++) {
        sum++;
    }
}


  9.  

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