Big O problem

Posted on 2006-05-04
Last Modified: 2011-09-20
for (i = 0; i<m; i++)
     for (j = 0; j <i; j++)

for (k = 0; k <m; k++)

boo() and blah() are methods that run at constant time.  My Professor did like a summation for the inside loop from i = 0 to i = m of i and he calculated the Big O in a weird way.  Can you tell me how to get the Big O of this.  
Question by:yattias
    LVL 14

    Expert Comment

    using this formula:

     i=2   j = 1
    ____  ____
    \        \
     |        |    i - 1
    /___   /___
      m       i

    somehow I got the value to be


    Just run some tests and You'll notice that the value is right, but I'm not sure how to count it.
    LVL 14

    Expert Comment

    I'd recommend to learn how to do that. Some resources can be found here:

    Author Comment

    huh? hmmm wikipedia explanation is slightly too advanced for me....can anyone give me an easier explanation?
    LVL 1

    Accepted Solution

    look at it this way:

    for (i = 0; i<m; i++)
         for (j = i; j > 0; j--)

    it's almost the same, except that j counts down from i to 1 (instead of from 0 up to i-1), so it makes the same number of iterations.
    this way:
    for i = 0, the blah() is executed 0 times
    for i = 1, the blah() is executed 1 times
    for i = m-1, the blah() is executed m-1 times

    so, if the outer loop is executed m times, you get:

    m * [(m-1) + (m-2) + ... + 1 + 0] =   ->
    (m*m -m) + (m*m -2m) + ... + m + 0 =   ->
    a*m*m + b*m + c

    which is a polynomial, so you get that it's O(m*m).

    the second loop is simply O(m), so for the whole code segment you get:

    O(m*m) + O(m) = O(m*m)
    LVL 30

    Expert Comment

    You should probably ask this in the Programming topic-area.
    LVL 14

    Expert Comment

    nicola_mazbar is correct

    look at the original code

    for (i = 0; i<m; i++)
         for (j = 0; j <i; j++)

    i = 0: blah() is executed 0 times
    i = 1: blah() is executed 1 times
    i = m-1: blah() is executed m-1 times

    total number of executions will be

    0 + 1 + 2 + ... + m-2 + m-1 = (m-1)(m-2) / 2 = a' m^2 + b' m + c' ==> O(m^2)

    Featured Post

    Live: Real-Time Solutions, Start Here

    Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

    Join & Write a Comment

    Suggested Solutions

    Title # Comments Views Activity
    strCount chalenge 3 36
    What is JNDI datasource in spring 1 21
    pairs challenge 5 33
    groovy example issue 10 40
    For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
    Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
    This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
    This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

    745 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now