Big-O analysis

This is a discussion on Big-O analysis within the C++ Programming forums, part of the General Programming Boards category; What is the Big-O analysis of this code? I think the code is doing a sort but I'm confused. Is ...

  1. #1
    Unregistered
    Guest

    Question Big-O analysis

    What is the Big-O analysis of this code? I think the code is doing a sort but I'm confused. Is this code comparing numbers for a sort and placing them in temporary cells?


    r = 0
    for i = 1 to N-1 do
    for j = i+1 to N do
    for k = 1 to j do
    r = r+1;

  2. #2
    Registered User snowy101's Avatar
    Join Date
    May 2002
    Posts
    22

    hmmm

    i got a few questions one is that in a loop two i think im gonna need more of the code to figure it out might just be me but the r = 0 and then the r = r + 1; should mean its in a loop cause r would be a counter the for stuff i would have to know what n and n-1 is basicly yeh ill need a bigger peice of code to work from to figure this out for yeh.
    Simple Programming

    :::: Error Message != A Smile ::::

  3. #3
    Registered User
    Join Date
    Jun 2002
    Posts
    7
    Sorry, but thats all the code I have. We are studing sorting algorithms and the Big-O notations. A question given us is to give a Big-O analysis of the following code. Maybe thats why I'm scratching my head because there isn't enough code provided?

  4. #4
    Registered User snowy101's Avatar
    Join Date
    May 2002
    Posts
    22

    i know this might sound..

    i know i might sound like a newbie but i gotta ask what exactly is the big-O?
    Simple Programming

    :::: Error Message != A Smile ::::

  5. #5
    Registered User
    Join Date
    Jun 2002
    Posts
    7
    I'll try to explain:

    [tag]

    Big-O (order of magnitude) function gives a rounded-off measurement of the run time for an algorithm (usually the worst-case run-time). The function f(n) in O(f(n)) is the upper bound on the value of the run-time T(n) for all n. The growth rate of T(n) <= the growth rate of f(n).
    Definition: T(n) is O(f(n)) iff (if and only if) there exist positive constants c and n0 such that T(n) <= c f(n), for all n >= n0.
    To calculate the big-O worst case run-time of an algorithm:
    1. Count each step (primitive operation) and come up with a polynomial (or exponential) in terms of the input size n.
    2. Take highest order term with n in it in the polynomial in step 1 and drop its leading coefficient to get f(n) in O(f(n)).
    Examples:
    T(n) = 3n + 2 is O(n) since 3n + 2 <= 4n for all n >= 2 where c=4 and n1 = 2.
    T(n) = 10n^2 + 4n + 2 is O(n^2) since 10n^2 + 4n + 2 <= 11n^2 for all n >= 5 where c=4 and n1 = 2.

    [/tag]

    Code:
    r = 0 
    for i = 1 to N-1 do 
    for j = i+1 to N do 
    for k = 1 to j do 
    r = r+1;

  6. #6
    Registered User raimo's Avatar
    Join Date
    Jun 2002
    Posts
    107

    Re: Big-O analysis

    Code:
    r = 0
    for i = 1 to N-1 do
        for j = i+1 to N do
            for k = 1 to j do
                r = r+1;
    Isn't this simply O(N^3) because there are three approx. N-loops?

  7. #7
    Registered User
    Join Date
    Jun 2002
    Posts
    7
    Yes, I believe you are right. Thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How Big is Too Big
    By kpreston in forum C Programming
    Replies: 4
    Last Post: 10-25-2008, 11:16 AM
  2. Big and little endian
    By Cactus_Hugger in forum C Programming
    Replies: 4
    Last Post: 10-12-2005, 08:07 PM
  3. Dev-C++ Profile Analysis
    By Orborde in forum C++ Programming
    Replies: 0
    Last Post: 05-28-2005, 02:37 AM
  4. rhetorical analysis and why it is for YOU!
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 03-30-2003, 02:11 PM
  5. Looking for some big C/C++ projects
    By C-Dumbie in forum C Programming
    Replies: 5
    Last Post: 09-16-2002, 01:18 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21