Big O problem

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

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

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.  
yattiasAsked:
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--)
          blah();

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)
0
 
StillUnAwareCommented:
using this formula:

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

somehow I got the value to be

O(m*m/2)

Just run some tests and You'll notice that the value is right, but I'm not sure how to count it.
0
 
StillUnAwareCommented:
I'd recommend to learn how to do that. Some resources can be found here:

http://en.wikipedia.org/wiki/Big_O_notation
0
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?
0
 
Mayank SAssociate Director - Product EngineeringCommented:
You should probably ask this in the Programming topic-area.
0
 
hoomanvCommented:
nicola_mazbar is correct

look at the original code

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

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)
0
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.