please see my comment on your first question regarding Big-O notation

http://www.experts-exchange.com/Programming/Q_21818669.html

http://www.experts-exchang

Solved

Posted on 2006-04-18

Will someone that is good with Big-O notation please help me find the Big O for these three program fragments?

sum = 0;

for(i=0; i<n; i++)

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

sum++;

sum = 0;

for(i=0; i<n; i++)

for(j=0; j<i*i; j++)

for(k=0; k<j; k++)

sum++;

sum = 0;

for(i=1; i<n; i++)

for(j=1; j<i*i; j++)

if(j%i == 0)

for(k=0; k<j; k++)

sum++;

sum = 0;

for(i=0; i<n; i++)

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

sum++;

sum = 0;

for(i=0; i<n; i++)

for(j=0; j<i*i; j++)

for(k=0; k<j; k++)

sum++;

sum = 0;

for(i=1; i<n; i++)

for(j=1; j<i*i; j++)

if(j%i == 0)

for(k=0; k<j; k++)

sum++;

8 Comments

http://www.experts-exchang

Check this link also

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

http://en.wikipedia.org/wi

And it's not allowed to ask a question twice for more than 500 points. This is the fifth time I see it spreaded all over the topic areas.

There are enough hints in the initial thread: http://www.experts-exchang

I think someone has already suggested this technique but let me try to help you understand it:

Take this one:

sum = 0;

for(i=0; i<n; i++)

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

sum++;

You need to count how many times 'sum++' is executed in terms of 'n'.

The 'i' loop will obviously cycle 'n' times so its

n * ...

The 'j' loop will cycle 'i' times so it will cycle like this:

0,1,2, ... n-1

To see how often 'sum++' is executed? It is clearly

0 + 1 + 2 + 3 + ... + (n-1)

What does that evaluate to?

Paul

But this question is already asked. People here all the time write about the site rules but nobody seems to observe them. Isn't this question for deletion? It was already asked for 500 points. And there are 5 threads opened so far.

I am here for less than 2 weeks, trying to get used with the rules but it seems that everyone interpret them as (s)he wants and even different in the same cases, maybe according to the Moon phases. ;)

>>I am here for less than 2 weeks, trying to get used with the rules but it seems that everyone interpret them as (s)he wants and even different in the same cases, maybe according to the Moon phases. ;)

You are right! I will fix this as soon as I can! I intend to level out the points between the questions to add up to 500. That is the usual route. I am at work right now, I'll do it this evening.

The ambiguities in the rules are, I hope, deliberate so that they can be interpreted either kindly or harshly. I try to take the kind approach because on this page a lot of the questions are from students who are often therefore newbies. It has been my experience that admin comments to homework questions generally just cause the question to be abandoned which helps no-one. I try to let the question mature for a while before enforcing the rules. The only people who suffer then are those who are only here for points :-)

I have noticed you around recently! I am impressed by the quality of your answers. Good work!

Paul

Title | # Comments | Views | Activity |
---|---|---|---|

Where is my core dump file in Ubuntu? | 12 | 414 | |

Why adding test code changes the build ? | 11 | 117 | |

How to create frequencies of a variable from SAS dataset? | 10 | 112 | |

C Language combined operators | 28 | 98 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**14** Experts available now in Live!