1
h06
CS24 F19
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 Fri 11/01 12:00AM Fri 11/08 11:59PM

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

INSTEAD OF TURNING IN THIS HOMEWORK, YOU WILL TAKE A QUIZ ON GAUCHOSPACE BY THE DUE DATE.
There is NO MAKEUP for missed homework assignments.
The quiz will be made available at least two days before the due date.


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.