comparing Algorithm complexity of two algorithm

Question

Before i ask this question here, I found that this site is the appropriate site to ask this question from here

I am having 2 algorithms Say A and B for same problem.

A is complexity is = 5nlogn
B is complexity is = n sqrt(n)

I want to find the value of n0 so that i can prove A is better than B.

I tried the below:

5nlogn/nsqrt(n) = 5logn / sqrt(n)

by putting 
 n = 512  ==> i got the answer. But i am not sure whether it is correct?

How can i do that?.

To be clear: i want to prove the below

A = BigO(B)

I'm not clear what you are trying to do, can you explain further? What does n0 represent? — codebox
– codebox, Commented Sep 3, 2015 at 6:09
@MohitJain.Please see the updated post. To be clear: i want to prove the below A = BigO(B) — backtrack
– backtrack, Commented Sep 3, 2015 at 6:12
@codebox .Please see the updated post. To be clear: i want to prove the below A = BigO(B) — backtrack
– backtrack, Commented Sep 3, 2015 at 6:12

amit · Accepted Answer · 2015-09-03 06:15:36Z

2

Not exactly.

You are looking for

5nlog(n) < nsqrt(n)
5nlog(n) / nsqrt(n) < 1
5log(n) / sqrt(n) < 1

From wolfram alpha, this is correct for all n > ~3500

As a side note, if you want to show 5nlog(n) is in O(nsqrt(n)), you can tweak the constants, and add a constant C:

5nlog(n) < C*nsqrt(n) for all n > n0

When choosing C=10, the above holds for all n>0

edited Sep 3, 2015 at 6:15

answered Sep 3, 2015 at 6:12

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

backtrack Over a year ago

Thank you the reply, But did you use base 2 for Log ?

backtrack Over a year ago

Thank amit, But i am not sure, What base should i use. When i use base10 i am getting different answer. :( So What must be the correct answer, Say if i have no = 512, 1024, 2048 and 4932

amit Over a year ago

@Backtrack I am not following the question, are you asking for which n0\in {512,1024,2048, 4932} the equations 5nlog(n) < nsqrt(n), n>n0 hold? The answer to this question is 4932, if that's what you're asking. If you are looking for lowest such n0, that's depend on the base you are using - and you need to ask your TA which base to use (or if you got the complexity from some algorithm, find it yourself)

backtrack Over a year ago

Can you please help me in this, I wan to pick the best n0 value, I tried with base10 and base2

backtrack Over a year ago

Why the answer is 4932, So you are saying that we should use log base 2. Is my understanding correct

|

Collectives™ on Stack Overflow

comparing Algorithm complexity of two algorithm

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related