Thread: Calculating Big O

  1. #1
    Registered User
    Join Date
    May 2017
    Posts
    7

    Calculating Big O

    Calculating Big O-bigoquestion-jpg
    Calculating Big O-bigosampletotals-png

    The second picture should be along the right hand side of the first picture. I apologize for not shrinking it before pasting.

    In the above program, I don't understand why both the inner loop total and total for the entire program includes fractions. Ie. 3/2n^2 -1/2n for the inner loop and 3/2n^2 +5/2n +3 for the total.
    For my answer, I multiplied inner loop total of (3n +1) by (n+1) which is the number of times the outer loop iterates to get a total of 3n^2+4n+1. Tack on 2 for initialization and return 0 for a grand total of 3n^2 +4n +3 rather than the equation given.

    From my answer, if I drop the coefficients and low order terms, I still end up with O(n^2) which is the correct answer.

    Also, what if the nested loop had a constant in the conditions, ie. for(int i=0; i<3; i++) such as below:


    Code:
    for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    printf("%d", arr[i]);
                   }
                printf("\n");
            }
    }
    
    
    In this case, I'd imagine that it is not quadratic but linear since the iterations in the nested loops are limited to a constant and would not increase as n increases.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Big-O only cares about the most dominant term.

    As n gets large, it really doesn't matter whether it's 3nē +4n +3 or 5nē +8n +7
    The result is still only O(Nē).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 05-10-2015, 06:57 AM
  2. calculating e
    By roelof in forum C Programming
    Replies: 11
    Last Post: 06-11-2011, 01:49 AM
  3. Calculating MPG
    By Robot Kris in forum C Programming
    Replies: 7
    Last Post: 09-08-2010, 08:29 PM
  4. calculating the mean
    By bartleby84 in forum C Programming
    Replies: 9
    Last Post: 08-27-2007, 11:47 AM
  5. Help with calculating
    By Moffia in forum Windows Programming
    Replies: 3
    Last Post: 08-05-2005, 01:21 AM

Tags for this Thread