Big O problem

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.  
Who is Participating?
nicola_mazbarConnect With a Mentor Commented:
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)
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.
I'd recommend to learn how to do that. Some resources can be found here:
Cloud Class® Course: MCSA MCSE Windows Server 2012

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

yattiasAuthor Commented:
huh? hmmm wikipedia explanation is slightly too advanced for me....can anyone give me an easier explanation?
Mayank SAssociate Director - Product EngineeringCommented:
You should probably ask this in the Programming topic-area.
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)
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.