Big O problem

Posted on 2006-05-04
Medium Priority
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

ID: 16609222
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

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


Author Comment

ID: 16609325
huh? hmmm wikipedia explanation is slightly too advanced for me....can anyone give me an easier explanation?
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!


Accepted Solution

nicola_mazbar earned 750 total points
ID: 16609838
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

by:Mayank S
ID: 16612252
You should probably ask this in the Programming topic-area.
LVL 14

Expert Comment

ID: 16612385
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

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
In this post we will learn different types of Android Layout and some basics of an Android App.
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
This video teaches viewers about errors in exception handling.
Suggested Courses
Course of the Month17 days, 13 hours left to enroll

830 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