How to compare O(log(d,n)) and O(n^(1/d))

Leon

Re: How to compare O(log(d,n)) and O(n^(1/d))

gcrhoads at yahoo.com

Re: How to compare O(log(d,n)) and O(n^(1/d))

Ajoy K Thamattoor

From:	Leon
Subject:	How to compare O(log(d,n)) and O(n^(1/d))
Date:	18 Jan 2005 12:30:28 -0800

O(log(d,n)): d is the base of log.

Thanks for any hints!

Best

From:	gcrhoads at yahoo.com
Subject:	Re: How to compare O(log(d,n)) and O(n^(1/d))
Date:	18 Jan 2005 18:35:36 -0800

Is this a homework question?

From:	Ajoy K Thamattoor
Subject:	Re: How to compare O(log(d,n)) and O(n^(1/d))
Date:	Wed, 19 Jan 2005 11:03:36 -0800

Leon wrote:
> O(log(d,n)): d is the base of log.

Use the limit
lt[n->inf] (n^b/a^n) (where a, b are real constants, a>1).
This limit has value 0.
If you now substitute log(n) for n and 2^a for a,
you'll get a limit relation which should give you the
asymptotic-growth comparison relationship.

Ajoy.