University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

CSC 477/677 Assignment 1

Due date: Wednesday, September 4, 2013, 2:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.

For each problem below, give the asymptotic complexity using, O, Θ, or Ω, whichever is appropriate.

  • Solve the following recurrences.
    1. F(n) ≥ F(n/3)+9
    2. G(n) ≤ 8G(n/2)+n3
    3. H(n) = H(n/2)+n2
    4. T(n) ≤ T(√ n)+1
    5. F(n) = F(n-2)+5n2
    6. G(n) ≤ G(n - log n) + log n
  • Determine the asymptotic time complexity, in terms of n, of each of these code fragments. 
    1. for(int i = n; i > 1; i = i/2)
    for(int j = 1; j < i; j++)
        cout << "Hello world" << endl;

    2. for(int i = 1; i < n; i++)
    for(int j = 1; j < n; j = 2*j)
        cout << "Hello world" << endl; 

    3. for(int i = n; i > 1; i = sqrt(i))
    cout << "Hello world" << endl;

    4. for(int i = n; i > 1; i = log(i))
    cout << "Hello world" << endl;
    • Back to Course Page