asked on 5/4/2006

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.

Java

Last Comment

hoomanv

5/5/2006

StillUnAware

5/4/2006

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.

StillUnAware

5/4/2006

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

http://en.wikipedia.org/wiki/Big_O_notation

yattias

5/4/2006

ASKER

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

ASKER CERTIFIED SOLUTION

nicola_mazbar

5/4/2006

THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.

View this solution by signing up for a free trial.

Members can start a 7-Day free trial and enjoy unlimited access to the platform.

See Pricing Options

Start Free Trial

Mayank S

5/5/2006

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

hoomanv

5/5/2006

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)