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  654 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
