# Week 4: Exercises

These are optional exercises that I suggest you try to practice the material we've learned so far.

## 1. Big O

For each pair of functions f and g, determine whether f(n) = O(g(n)).

f(n)

g(n)

10n + 4

4n + 10

1000

1

|sin(n)|

1

1

|sin(n)|

2n + 1

2n

22n

2n

n16

2n

log2(n)

log10(n)

2^sqrt(n)

n

[log(n)]10

n0.1

sqrt(n)

nsin n

nlog 5

5log n

## 2. Complexity Squared

Is it true that for all eventually positive functions f, f(n) = O(f(n)2)?

## 3. Maximum Bound

Prove that for all asymptotically positive functions f and g,

f(n) + g(n) = O(max(f(n), g(n)))

## 4. Neither Grows Faster

Give an example of two asymptotically positive continuous functions f and g for which neither f(n) = O(g(n)) nor g(n) = O(f(n)).

## 5. Copy a File

Write a program copy that takes two filenames as command-line arguments and copies the first (a text file) to the second. If the second file already exists, it should be overwritten. For example:

\$ copy prog.pas prog2.pas

## 6. Largest Prime Factor

Solve Project Euler’s Problem 3.

## 7. 10001st Prime

Solve Project Euler’s Problem 7.

## 8. Summation of primes

Solve Project Euler’s Problem 10.

## 9. Lexicographic Comparison

Write a function that takes two strings s and t and returns an integer which is

• 1 if s > t

• 0 if s = t

• -1 if s < t

where comparisons are performed in lexicographic (dictionary) order. You should treat uppercase and lowercase letters as the same, and ignore all non-alphabetic characters (i.e. act as if that they are absent from the strings). Do not use the built-in string comparison operators < or >.

## 10. Random Permutation

Write a program that reads a string and writes a random permutation of the characters in the string. All permutations should be equally likely. Your program should run in time O(n), where n is the length of the input string.

## 11. Digits of π

Write a program that reads a number n as input, and prints out the first n digits of π.

Hint: π / 4 = 1 – (1/3) + (1/5) - (1/7) + ...

## 12. Overlapping Segments

Write a program that reads four real numbers a, b, c, and d. The program should write 'overlap' if the line segments [a, b] and [c, d] touch or overlap, or 'disjoint' otherwise.

Input:

3 10 8 15

Output:

overlap