[Ap0C552]

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

[KYA]

Shameless plug alert!


Check out my Big O tutorial. After giving that a quick perusal, these will be easy for you.

[Ap0C552]

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

[blackcompe]

I agree with you. I think it's exactly n^2 + 2n + 1.

[KYA]

Except you generally don't write big O like that. You drop the lower order terms, so it's just n²

[blackcompe]

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

[Ap0C552]

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.

[blackcompe]

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).

[Ap0C552]

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).

[blackcompe]

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?

[Ap0C552]

Well it did not says theta or big theta it just gave the symbol circle with a crossbar, is that theta or big theta?

[blackcompe]

I'd have to see the question to give my best judgement. Big theta is denoted by a bigger theta symbol.

[sepp2k]

blackcompe, 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.

[Ap0C552]

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?

[sepp2k]

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.