CSC 210 Exercises on Asymptotic Analysis

COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Exercises on Asymptotic Analysis

Due Date: Monday, October 3 (at start of class session)

Objectives

To gain understanding of the methods and results of asymptotic analysis.
To gain practice with proof techniques involving Big-Oh arithmetic.
To become familiar with closed form solutions of summations.

Assignment

Answer the following questions, either in handwritten form or using some program that supports mathematical notation. In the following, assume that "log n" means "log₂ n".

Order the following list of functions by their Big-Oh time complexity, such that if function f(n) is above or to the left of g(n), then f(n) = O(g(n)). (I.e., put them in order, fastest to slowest; more formally, order them by growth rate, from most slowly growing to most quickly growing.)
1. 6n log n + 2n
2. ( 1 / 3 )ⁿ
3. n ⁿ
4. log log n
5. log ² n [See the textbook, p. 155, on the meaning of the notation "log ^c n".]
6. 1 / n
7. 2¹⁰
8. n - n ³ + 7n ⁵
9. n / log n
10. n ! [That's n factorial.]
11. 2^{log n}
12. 2ⁿ
13. 3n + 100 log n
Algorithm A uses 10n log n operations, while algorithm B uses n ² operations.
1. Determine the value n₀ such that A is better than B for n >= n₀.
2. Repeat the problem assuming B uses n sqrt(n) operations.

For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t assuming that the algorithm to solve the problem takes f(n) microseconds. (Some entries have already been completed as examples.)

	1 Second	1 Hour
log n	approx. 10³⁰⁰⁰⁰⁰
sqrt(n)
n
n log n
n²
n³
2ⁿ
n !		12

Prove or disprove:
1. 12 is O( 1 ).
2. 7n + 3n² - 2 is O( n³ ).
3. max( n³, 10n² ) is O(n²).
4. 3n log n is Big-Omega( n ).
5. f(n) = n² for even n >= 0 is O( n² ).
  
  n³ for odd n >= 1
6. 2^{n + 1} is O( 2ⁿ ).
7. If d(n) is O(f(n)) and e(n) is O(g(n)), then the product d(n)e(n) is O(f(n)g(n)).
Characterize the following summations (exactly) in terms of n:
1. 5 + 5 + 5 + 5 + . . . + 5
  
  -- -- -- --- ---
  
  2 4 8 16 2ⁿ
2. Sigma _{1 <= i <= n} ( 3i + 4 ) [where Sigma is the summation symbol].

Give a Big-Oh characterization, in terms of n, of the running time of each of the following Java methods.

        public void ExA( int n ) {
            int a;
            for ( int i = 0; i < n; i += 2 )
                a = i;
        }

        public void ExB( int n ) {
            int a;
            for ( int i = 0; i < n * n; i++ )
                a = i;
        }

        public void ExC( int n ) {
            int a;
            for ( int i = 0; i < n; i++ )
                for ( int j = 0; j <= i;  j++ )
                    a = i;
        }

        public void ExD( int n ) {
            int a;
            for ( int i = 0; i < n * n; i++ )
                for ( int j = 0; j <= i;  j++ )
                    a = i;
        }

        public void ExE( int n ) {
            int a;
            for ( int i = 0; i < n; i++ )
                for ( int j = 0; j <= n - i;  j++ )
                    a = i;
        }

        public void ExF( int n ) {
            int a;
            for ( int i = 1; i < n; i *= 2 )
                a = i;
        }

1. Give an example of a positive function f(n) such that f(n) is neither O(n) nor Big-Omega( n ).
2. Would the function be Big-Omega( n ) if Big-Omega were redefined as follows?
  
  f(n) is Big-Omega of g(n) if there is a real constant c > 0 such that f(n) >= c g(n) for infinitely many values of n.
  
  Provide a proof for your conclusion.
The following conversation was overheard between a programmer and a computer scientist:

Programmer:

I just wrote a really fast program to solve the WOW problem. I wrote it in assembler, optimized every loop, and used every special instruction available on the Quadrium-7 processor.

Computer Scientist

How fast is it?

Programmer:

Well, for 10 BogoUnits, it took 10 seconds to find the optimum, and for 11, it took 20 seconds, and for 12, it took 40 seconds, and for 13, it took 80 seconds, and so on.

Computer Scientist

But that's really slow! I have a O( n³ ) algorithm, which is much faster.

Programmer:

Faster?! I tried your program and it took 1000 seconds for 10 BogoUnits. How can you claim your method is faster?
1. Estimate how long it would take the Computer Scientist's algorithm to solve the problem for 20 BogoUnits.
2. Estimate how long it would take the Programmer's program to solve the problem for 20 BogoUnits.
3. What additional information do you need to decide which solution is in fact better for the actual problem?

Submission

Submit a hardcopy of your solutions in hard copy form to the instructor by the due date specified.

f(n) =	n²	for even n >= 0	is O( n² ).
	n³	for odd n >= 1