certain big-o problem

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 1652 Views - Last Post: 06 October 2011 - 12:16 PM

#1 Ap0C552  Icon User is offline

  • D.I.C Regular

Reputation: -7
  • View blog
  • Posts: 318
  • Joined: 08-December 10

certain big-o problem

Posted 02 October 2011 - 12:44 PM

Here are two algorithms I am working on to figure big-o

The first is


sum=0;

for (int i=n;i>=0;i++)
{

sum*=x;
sum+=a[i];

}

return sum




For this one I figured out f(n)=2(n+1)+1=2n+3 Does this seem correct?


The second one is even more trouble for me



sum=a[0]+a[1]*x;

for(int i =2; i<=n ; i++)
{

temp =x;
   for  (int j=2; j<= i ;j++)
      {
       temp*= x;
      }
    
sum+= a[i] * temp;

}




this one has me REALLY confused

Is it basically a form of this in a way?


for(int i=0;i<=n;n++)
{
     for(int j=0;j<=i;j++)
     {

     }


}



So would the big-o for this be??

Any help is greatly appreciated! Thanks.

This post has been edited by Ap0C552: 02 October 2011 - 12:46 PM


Is This A Good Question/Topic? 0
  • +

Replies To: certain big-o problem

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • Joined: 14-September 07

Re: certain big-o problem

Posted 02 October 2011 - 01:12 PM

Shameless plug alert!


Check out my Big O tutorial. After giving that a quick perusal, these will be easy for you.
Was This Post Helpful? 0
  • +
  • -

#3 Ap0C552  Icon User is offline

  • D.I.C Regular

Reputation: -7
  • View blog
  • Posts: 318
  • Joined: 08-December 10

Re: certain big-o problem

Posted 02 October 2011 - 02:02 PM

Thanks for the link, I just read it.

Those this mean that the second algorithm would be n2+2n+1?

Can someone confirm or deny that?

Thanks
Was This Post Helpful? 0
  • +
  • -

#4 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,536
  • Joined: 05-May 05

Re: certain big-o problem

Posted 02 October 2011 - 02:14 PM

I agree with you. I think it's exactly n^2 + 2n + 1.
Was This Post Helpful? 0
  • +
  • -

#5 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • Joined: 14-September 07

Re: certain big-o problem

Posted 02 October 2011 - 02:16 PM

Except you generally don't write big O like that. You drop the lower order terms, so it's just n2
Was This Post Helpful? 0
  • +
  • -

#6 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,536
  • Joined: 05-May 05

Re: certain big-o problem

Posted 02 October 2011 - 03:34 PM

KYA is right. The algorithm is actually Big-Theta n^2 + 2n + 1, which is then Big-Oh n^2.
Was This Post Helpful? 0
  • +
  • -

#7 Ap0C552  Icon User is offline

  • D.I.C Regular

Reputation: -7
  • View blog
  • Posts: 318
  • Joined: 08-December 10

Re: certain big-o problem

Posted 03 October 2011 - 01:48 PM

Oh dear I had a question that I think relates to this on a quiz today.

They gave us an algorithm and asked us to describe the running time of it in terms of f(n) and said to simplify.

Then they asked a subsequent question that was along the line of "Explain f(n) in simpler terms using theta". I had no clue what that meant.
Was This Post Helpful? 0
  • +
  • -

#8 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,536
  • Joined: 05-May 05

Re: certain big-o problem

Posted 03 October 2011 - 01:55 PM

I'm not all that knowledgeable in this field, but I would have assumed that meant to show that f(n) is less than or equal to and greater than or equal to g(n).
Was This Post Helpful? 0
  • +
  • -

#9 Ap0C552  Icon User is offline

  • D.I.C Regular

Reputation: -7
  • View blog
  • Posts: 318
  • Joined: 08-December 10

Re: certain big-o problem

Posted 03 October 2011 - 04:00 PM

Ya but that would be asking to "show that f(n) is in theta g(n)"

This is how that question was always worded, why would they change the wording? To be assholes? (I think this is a possibility LOL).
Was This Post Helpful? 0
  • +
  • -

#10 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,536
  • Joined: 05-May 05

Re: certain big-o problem

Posted 03 October 2011 - 05:10 PM

I really don't know. Actually your question said "theta," not "big-theta," so I'm probably wrong. Why don't you send your professor or TA an email?
Was This Post Helpful? 0
  • +
  • -

#11 Ap0C552  Icon User is offline

  • D.I.C Regular

Reputation: -7
  • View blog
  • Posts: 318
  • Joined: 08-December 10

Re: certain big-o problem

Posted 03 October 2011 - 05:37 PM

Well it did not says theta or big theta it just gave the symbol circle with a crossbar, is that theta or big theta?
Was This Post Helpful? 0
  • +
  • -

#12 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,536
  • Joined: 05-May 05

Re: certain big-o problem

Posted 03 October 2011 - 06:26 PM

I'd have to see the question to give my best judgement. Big theta is denoted by a bigger theta symbol.
Was This Post Helpful? 0
  • +
  • -

#13 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: certain big-o problem

Posted 04 October 2011 - 05:35 AM

View Postblackcompe, on 03 October 2011 - 12:34 AM, said:

KYA is right. The algorithm is actually Big-Theta n^2 + 2n + 1, which is then Big-Oh n^2.


That's a bit misleading. Theta(n^2 + 2n + 1) is exactly the same as Theta(n^2 + 2n + 1), in the same way that O(n^2 + 2n + 1) is exactly equal to O(n^2).

Ap0C552 said:

Then they asked a subsequent question that was along the line of "Explain f(n) in simpler terms using theta". I had no clue what that meant.


If you calculated f(n) to be a*n^2 + b*n + c, you can then say that f(n) is in Theta(n^2), which is simpler because you dropped a, b*n and c.
Was This Post Helpful? 0
  • +
  • -

#14 Ap0C552  Icon User is offline

  • D.I.C Regular

Reputation: -7
  • View blog
  • Posts: 318
  • Joined: 08-December 10

Re: certain big-o problem

Posted 04 October 2011 - 01:37 PM

So if f(n)=n^2+1 and they say express f(n) in simpler terms using theta they just want to to express is as theta f(n)=n^2?
Was This Post Helpful? 0
  • +
  • -

#15 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: certain big-o problem

Posted 04 October 2011 - 01:43 PM

It would be written as f(n)=Theta(n^2) (or f(n) \in Theta(n^2) depending on which notation your class uses), but yes, they want you to simplify it to n^2.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2