# 600.488 Homework Assignment 1

### 50 Points

1. Sort the following list of functions of n, so that whenever f is before g, then f=O(g). Functions that are Theta(*) of one another should be listed together.
• n
• 2n
• 7
• log n
• 2(3log n)
• n(0.1)
• (log n)2
• log log n
• 2(log n)
• n2
• n(log 3)
• 2(log log n)
2. Show that if f(n) is O(d(n)) and g(n) is O(e(n)), then f(n) + g(n) is O(d(n) + e(n)).
3. Describe three different ways to represent a two-dimensional point. For each representation, describe a short method for determining if this point is above or below the x-axis.
4. Suppose you are given two polygonal chains, A and B, each represented as a sequence of two-dimensional points. Suppose further that the sequence of points in both A and B are ordered by increasing x-coordinates, as shown below. Describe an efficient method for determining if the chains A and B ever cross each other (i.e., intersect). What is the running time of your method?

5. Suppose you are given a polygonal chain, A, as in the previous problem, i.e., a chain whose points are ordered by x-coordinates. Suppose futher that A is already in your computer's main memory and you know that A is represented using an array. Describe a very fast method for determining if a given vertical line, L, intersects A, and if so, exactly where it intersects A. What is the running time of your method?