Algorithm Analysis: Big O.... i think?

Discussion in 'C Programming' started by G G, Sep 14, 2013.

  1. G G

    G G Guest

    O(log n) < O(n) < O(nLog n) < O(n^2) < O(n^3) < O(2^n) in running time.
    2 2


    my question has to do with actually determining that Big-O type.

    Questions:

    n represents the number of data items?

    given a loop:
    for (int i =0; i<1000: i++)
    {
    int a = a + i;
    }
    this would be a O(n), because as the number of items increases the time
    to run increase linearly?

    what about:
    for ( int i=0: i<1000: i++)
    {
    int a = a + i;
    int t = t + i;
    }
    are we only concerned of the number of item or will the two assignment
    statement change the analysis in some way?

    what about:

    for (int i =0; i <1000; i++)
    {
    for ( int t =1; i < 1000; i++)
    {
    int a = a+i+t;
    }
    }

    is this O(n^2)? why? how do you come up with that?

    what are example of something being O(n/2), or O(log n )?
    2

    and how do you know that they are that?
     
    G G, Sep 14, 2013
    #1
    1. Advertisements

  2. G G

    Eric Sosman Guest

    ... hence, not much to do with the C programming language.
    A forum like comp.programming might be better suited for questions
    about programming in general, as opposed to questions about
    programming in a particular language or in a particular environment.
     
    Eric Sosman, Sep 14, 2013
    #2
    1. Advertisements

  3. Use a fixed-width font if you want to write subscripts that way, but
    people will understand log2(n) just as well (and, in any case, the base
    does not matter!).
    This belongs in comp.programming. Rather than my setting follow-ups
    (which does not always work) I strongly encourage you to post again
    there.

    <snip>
     
    Ben Bacarisse, Sep 14, 2013
    #3
  4. G G

    G G Guest

    ok
     
    G G, Sep 14, 2013
    #4
  5. G G

    G G Guest

    Please don't not discuss, post, here. Ben tells me this is a really not the proper place for this discussion.

    He gave me a proper spot to post. I have posted this question over on comp.programming

    thanks everyone,

    g.
     
    G G, Sep 14, 2013
    #5
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.