# certain big-o problem

• (2 Pages)
• 1
• 2

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

### #1 Ap0C552

• D.I.C Regular

Reputation: -6
• Posts: 321
• 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

• g++ jameson.cpp -o beverage

Reputation: 3145
• Posts: 19,185
• Joined: 14-September 07

## Re: certain big-o problem

Posted 02 October 2011 - 01:12 PM

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

### #3 Ap0C552

• D.I.C Regular

Reputation: -6
• Posts: 321
• Joined: 08-December 10

## Re: certain big-o problem

Posted 02 October 2011 - 02:02 PM

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

Can someone confirm or deny that?

Thanks

### #4 blackcompe

• D.I.C Lover

Reputation: 1156
• Posts: 2,538
• 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.

### #5 KYA

• g++ jameson.cpp -o beverage

Reputation: 3145
• Posts: 19,185
• 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

### #6 blackcompe

• D.I.C Lover

Reputation: 1156
• Posts: 2,538
• 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.

### #7 Ap0C552

• D.I.C Regular

Reputation: -6
• Posts: 321
• 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.

### #8 blackcompe

• D.I.C Lover

Reputation: 1156
• Posts: 2,538
• 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).

### #9 Ap0C552

• D.I.C Regular

Reputation: -6
• Posts: 321
• 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).

### #10 blackcompe

• D.I.C Lover

Reputation: 1156
• Posts: 2,538
• 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?

### #11 Ap0C552

• D.I.C Regular

Reputation: -6
• Posts: 321
• 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?

### #12 blackcompe

• D.I.C Lover

Reputation: 1156
• Posts: 2,538
• 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.

### #13 sepp2k

• D.I.C Lover

Reputation: 2242
• Posts: 3,440
• Joined: 21-June 11

## Re: certain big-o problem

Posted 04 October 2011 - 05:35 AM

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.

### #14 Ap0C552

• D.I.C Regular

Reputation: -6
• Posts: 321
• 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?

### #15 sepp2k

• D.I.C Lover

Reputation: 2242
• Posts: 3,440
• 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.