Algorithms

Page 1 of 1

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

#1 AbuJaFaR

• D.I.C Regular

Reputation: 13
• Posts: 330
• Joined: 13-December 07

Algorithms

Posted 23 March 2009 - 07:26 AM

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?

Is This A Good Question/Topic? 0

Replies To: Algorithms

#2 AbuJaFaR

• D.I.C Regular

Reputation: 13
• Posts: 330
• Joined: 13-December 07

Re: Algorithms

Posted 24 March 2009 - 02:41 PM

No one ? O_O

#3 bryanchen

Reputation: 0
• Posts: 4
• Joined: 06-February 09

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.

#4 AbuJaFaR

• D.I.C Regular

Reputation: 13
• Posts: 330
• Joined: 13-December 07

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