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

x
?
Solved

Big O

Posted on 2006-04-18
9
Medium Priority
?
560 Views
Last Modified: 2010-04-15
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
Comment
Question by:tjn92
8 Comments
 
LVL 11

Accepted Solution

by:
asian_niceguy earned 200 total points
ID: 16484683
please see my comment on your first question regarding Big-O notation
http://www.experts-exchange.com/Programming/Q_21818669.html
0
 
LVL 12

Expert Comment

by:rajeev_devin
ID: 16484813
0
 
LVL 11

Expert Comment

by:WelkinMaze
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 16

Expert Comment

by:PaulCaswell
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

by:WelkinMaze
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

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

Expert Comment

by:PaulCaswell
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

by:WelkinMaze
ID: 16488620
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

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

830 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question