Homework 5
CS 5046 (Spring 2011)

Assigned on April 25, 2011
Due by 4pm, May 2, 2011
Submit by email to murali AT cs DOT vt DOT edu

This homework deals with algorithm analysis. You do not need to implement any code to solve these problems. You can write the solutions to the homework and email them to me.

Problem 1
(10 points) Prove that n/2 = O(n).
Problem 2
(10 points) Prove that 4n - 10 = O(n).
Problem 3
(10 points) Prove that 4n - 10 = Ω(n).
Problem 4
(10 points) Is n2 = O(n)? Either prove the statement or explain why it is false.
Problem 5
(20 points) Prove that for every positive integer k, nk = O(nk + 1). For example, this statement says that an algorithm that runs in time O(n4) is slower than an algorithm that runs in time O(n3).
Problem 6
(40 points) We know that the sum of the first n positive integers is n(n + 1)/2. What is the sum of the first n odd numbers, i. e., the sum of 1, 3, 5, ..., 2n - 3, and 2n - 1? Prove your answer. You may find it helpful to consider the sum of the first 2n positive integers and then think about what numbers you need to remove to obtain the sum of the first n odd numbers.
Last modified: Mon Apr 25 13:52:47 EDT 2011