Homework - Big O analysis

Question

My homework involves Big O analysis and I think I've got the hang of it, but I'm not 100% sure. Would any of you lovely people mind taking a look and telling me if I'm on the right track?

The assignment is below. For questions 1 and 3, my analysis and answers are on the right, after the // marks. For question 2, my analysis and answers are below the algorithm type.

Thanks in advance for your help! :-)

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?

Answer 1

I looked at your questions 1 to 3 and its looks alright.

Follow these rules and check for yourself:

1) Multiplicative constants can be omitted, Example 50n^2 simplifies to n^2

2) n^a dominates n^b if a>b Example n^3 dominates n^2, so n^3 + n^2 + n ,simplifies to n3

3) Any exponential dominates any polynomial Example 3^n dominates n^5 Example 2^n dominates n^2+5n+100

4) Any polynomial dominates any logarithm Example n dominates (log n)3

As for Question 4 use below as a guide (from least to greatest):

Log2 n < n < n log2 n < n^2 < n^3 < 2^n

Answer 2

the answer for the (b) of the time calculation is wrong. you can not assume one of the n as constant.So nlogn becomes 1log1 which means log1 is 0. so 0.

so that answer is 100 log100 operations comparision with 500log500 ...

coming to the least to greatest. b is 4 and a is 5. c,e,k are competition for the position 6 and 7 and 8. 1,2,3 positions given by you are correct.9,10,11 are correct.

i will check some analysis over 6,7,8 and let you know..

if you need any clarrification over my answer you can comment on that ..