 # 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 StillUnAware 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 I'd recommend to learn how to do that. Some resources can be found here:

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

huh? hmmm wikipedia explanation is slightly too advanced for me....can anyone give me an easier explanation? nicola_mazbar  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. Mayank S You should probably ask this in the Programming topic-area. hoomanv 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) Java

Java is a platform-independent, object-oriented programming language and run-time environment, designed to have as few implementation dependencies as possible such that developers can write one set of code across all platforms using libraries. Most devices will not run Java natively, and require a run-time component to be installed in order to execute a Java program.

102K
Questions
--
Followers
--
Top Experts
Get a personalized solution from industry experts

TRUSTED BY           