tjn92
asked on
Big O
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++;
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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: https://www.experts-exchange.com/questions/21816779/Algorithm-analysis.html
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: https://www.experts-exchange.com/questions/21816779/Algorithm-analysis.html
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
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
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. ;)
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. ;)
oops, sorry, I overlooked it.
to (n-1) is correct.
to (n-1) is correct.
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
>>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
Thanks for the answer, Paul!
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
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
http://en.wikipedia.org/wiki/Big_O_notation