Homework 5
CS 5046 (Spring 2007)

Assigned on April 12, 2007
Due by 11AM, April 19, 2007
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 hand them to me before class starts.

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: Wed Apr 11 23:08:11 EDT 2007