[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
Solved

# Big O

Posted on 2006-04-18
Medium Priority
560 Views
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++;
0
Question by:tjn92

LVL 11

Accepted Solution

asian_niceguy earned 200 total points
ID: 16484683
http://www.experts-exchange.com/Programming/Q_21818669.html
0

LVL 12

Expert Comment

ID: 16484813
0

LVL 11

Expert Comment

ID: 16485107
You've already asked this question. You've claimed that you don't want someone else to do the work instead of you.
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-exchange.com/Programming/Programming_Languages/C/Q_21816779.html
0

LVL 16

Expert Comment

ID: 16486229
tjn92,

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
0

LVL 11

Expert Comment

ID: 16486269
Paul, I've suggested it, it has to be 0,1,2,..., (n-2) instead to (n-1) but it doesn't so much matter.
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. ;)
0

LVL 11

Expert Comment

ID: 16486478
oops, sorry, I overlooked it.
to (n-1) is correct.
0

LVL 16

Expert Comment

ID: 16488553
WelkinMaze,

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

LVL 11

Expert Comment

ID: 16488620

I just asked you since I knew you're moderating several TAs.
Apart from that I like your comments, often seem near to my understanding.

Thanks again!
WM
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoā¦
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address.Ā This address might be address of another variable/address of devices/address of fuā¦
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
###### Suggested Courses
Course of the Month18 days, 2 hours left to enroll