• C

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++;
tjn92Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

asian_niceguyCommented:
please see my comment on your first question regarding Big-O notation
http://www.experts-exchange.com/Programming/Q_21818669.html
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
rajeev_devinCommented:
0
WelkinMazeCommented:
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
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

PaulCaswellCommented:
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
WelkinMazeCommented:
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
WelkinMazeCommented:
oops, sorry, I overlooked it.
to (n-1) is correct.
0
PaulCaswellCommented:
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
WelkinMazeCommented:
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
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.