问作业-大O分析

EN

1.For each of the following program fragments, give a Big-Oh analysis of the running time in terms of N:
    (a) // Fragment (a)
        for ( int i = 0, Sum = 0; i < N; i++ )      // N operations
            for( int j = 0; j < N; j++ )            // N operations
                Sum++;                              // Total: N^2 operations  =>  O(N^2)

    (b) // Fragment (b)
        for( int i = 0, Sum = 0; i < N * N; i++ )   // N^2 operations
            for( int j = 0; j < N; j ++ )           // N operations
                Sum++;                              // Total: N^3 operations  =>  O(N^3)

    (c) // Fragment (c)
        for( int i = 0, Sum = 0; i < N; i++ )       // N operations
            for( int j = 0; j < i; j ++ )           // N-1 operations
                Sum++;                              // Total: N(N-1) = N^2 – N operations  =>  O(N^2)

    (d) // Fragment (d)
        for( int i = 0, Sum = 0; i < N; i++ )       // N operations
            for( int j = 0; j < N * N; j++ )        // N^2 operations 
                for( int k = 0; k < j; k++ )        // N^2 operations 
                    Sum++;                          // Total: N^5 operations  =>  O(N^5)

2. An algorithm takes 0.5 milliseconds for input size 100. How long will it take for input size 500 if the running time is:
    a. Linear
        0.5 *5 = 2.5 milliseconds

    b. O( N log N)  
        O (N log N) – treat the first N as a constant, so O (N log N) = O (log N)
        Input size 100 = (log 100) + 1 = 2 + 1 = 3 operations
        Input size 500 = (log 500) + 1= 2.7 + 1 = 3.7 ≈ 4 operations
        Input size 100 runs in 0.5 milliseconds, so input size 500 takes 0.5 * (4/3) ≈ 0.67 milliseconds

    c. Quadratic        
        Input size 100 in quadratic runs 100^2 operations =   10,000 operations
        Input size 500 in quadratic runs 500^2 operations = 250,000 operations = 25 times as many
        Input size of 100 runs in 0.5 milliseconds, so input size of 500 takes 25 * 0.5 = 12.5 milliseconds

    d. Cubic
        Input size 100 in quadratic runs 100^3 operations =     1,000,000 operations
        Input size 500 in quadratic runs 500^3 operations = 125,000,000 operations = 125 times as many
        Input size of 100 runs in 0.5 milliseconds, so input size of 500 takes 125 * 0.5 = 62.5 milliseconds


3. Find the Big-O for the following:
    (a) f(x) = 2x^3 + x^2 log x             // O(x^3)
    (b) f(x) = (x^4 – 34x^3 + x^2 -20)      // O(x^4)
    (c) f(x) = x^3 – 1/log(x)               // O(x^3)

4. Order the following functions by growth rate: (1 is slowest growth rate; 11 is fastest growth rate)
__6_ (a) N
__5_ (b) √N
__7_ (c) N^1.5
__9_ (d) N^2
__4_ (e) N log N
__2_ (f) 2/N        
_11_ (g) 2^N
__3_ (h) 37
_10_ (i) N^3
__1_ (j) 1/ N^2
__8_ (k) N^2 /log N


* My logic in putting (j) and (f) as the slowest is that as N grows, 1/N^2 and 2/N decrease, so their growth rates are negative and therefore slower than the rest which have positive growth rates (or a 0 growth rate in the case of 37 (h)). Is that correct?