1
h06
CS24 S19
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h06: Chapter 1: Runing Time Analysis

ready? assigned due points
true Wed 05/08 09:30AM Tue 05/14 06:00PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the lowest scores (if you have zeros, those are the lowest scores.)


Please:

  • No Staples.
  • No Paperclips.
  • No folded down corners.

Complete your reading of Chapter 1, Section 1.2. If you don’t have a copy of the textbook yet, there is one on reserve at the library under “COMP000-STAFF - Permanent Reserve”).

    1. (10 pts) What is the Big-O time complexity of the following code:
    for(int i=0; i<N; i+=2) {
    	...constant time operations...
    }
    
    Justify your answer.
    2. (10 pts) What is the Big-O time complexity of the following code:
    for(int i=1; i<N; i*=2) {
    	...constant time operations...
    }
    
    Justify your answer.
    3. (20 pts) What is the Big-O time complexity of the following code:
    int x = 10;
    for(int i=1; i<N; i*=2) {
    	for(int j=0; j<N; j+=2) {
    		x++;
    	}
    }
    
    4. (10 pts) Provide a link to your github repo for pa01. Analyze the Big-O complexity of the insert, delete and search methods of your implementation of the CardList (linked list class). Assume that Alice and Bob each have exactly N cards. Provide your analysis here. As a challenge problem, analyze the Big-O complexity of your entire game.