Hehe.We have a lot of exercises so Im going to post them here when I get stuck.

Im good at the Hamilton paths etc, but at the notations Im really weak so I need help.

Hear my thought first and correct me or propose a better solution.

After the ^ symbol is the exponent.Before is the base.

Is it correct or not that (n^a + n^b ) = Θ(n^ab ) : a,b both positive ints numbers. (dont know how to translate it )

My thought :

The symbol Θ tells me that :

Θ(g(n))={ f(n) : there are positive ints number c1,c2 and n0 for which

0<= c1g(n) <= f(n)<=c2g(n) for every n>=n0}

So that f(n) is between c1g(n) and c2g(n) ,after a point n0, in a graphic design.

So, whats left is to prove it. If I take a=1 and b=1, c1=1 and c2=4 and design the functions the f function goes between the other two.So its correct.

So other thoughts?

## 3 Replies - 785 Views - Last Post: 28 March 2009 - 08:26 AM

##
**Replies To:** Algorithms

### #3

## Re: Algorithms

Posted 28 March 2009 - 06:58 AM

Off the top of my head (and it's been awhile since I touched these):

If n^a + n^b, wouldn't the efficiency be n^x, where x is the larger of 'a' and 'b'?

Remember the basics of analyzing efficiency classes? The performance is dominated by the largest polynomial. If a and b are the same value, then it just becomes 2n^a, which simplifies to n^a because of the proof that you provided.

If n^a + n^b, wouldn't the efficiency be n^x, where x is the larger of 'a' and 'b'?

Remember the basics of analyzing efficiency classes? The performance is dominated by the largest polynomial. If a and b are the same value, then it just becomes 2n^a, which simplifies to n^a because of the proof that you provided.

### #4

## Re: Algorithms

Posted 28 March 2009 - 08:26 AM

Hehe, thnx for the reply. But I have already give my assignment.So dont really think about it

Page 1 of 1