My Math Forum Big Oh Notations Help

 Applied Math Applied Math Forum

 September 18th, 2008, 03:55 PM #1 Newbie   Joined: Sep 2008 Posts: 2 Thanks: 0 Big Oh Notations Help I was wondering if I could get help on proving one of the Big Oh rules, specifically the Transitive Rule which states: If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)) So far this is what I have: there exists c1 and n1 f(n) <= c1 * g(n) for all n >= n1 g(n) <= c1 * h(n) for all n>= n1 therefore f(n) = h(n) and therefore O(h(n)) Would this be correct?
September 19th, 2008, 04:54 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Big Oh Notations Help

Quote:
 Originally Posted by gear2d Would this be correct?
No. f(n + 10) is O(n), and n is O(n^2), but n^2 is not equal to n + 10.

f(n) <= c1 * g(n) for all n >= n1
g(n) <= c2 * h(n) for all n>= n2
so
f(n) <= c1 * c2 * h(n) for all n >= max(n1, n2)

 September 19th, 2008, 11:28 AM #3 Newbie   Joined: Sep 2008 Posts: 2 Thanks: 0 Re: Big Oh Notations Help Thanks CRGreathouse. But I was wonder where you say max(n1, n2), should you not do the same thing with c1 and c2?
September 19th, 2008, 12:10 PM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Big Oh Notations Help

Quote:
 Originally Posted by gear2d Thanks CRGreathouse. But I was wonder where you say max(n1, n2), should you not do the same thing with c1 and c2?
No, you're just substituting "c2 * h(n)" for "g(n)" by transitivity. Suppose f(x) = x, g(x) = x/2 when x > 3, and h(x) = x/6 when x > 100. f(x) = 2g(x) when x > 3, g(x) = 3h(x) when x > 100, and f(x) = 6h(x) when x > 100.

 September 20th, 2008, 08:00 AM #5 Newbie   Joined: Sep 2008 Posts: 4 Thanks: 0 Re: Big Oh Notations Help I was wondering how would you go about doing it with the Log of a Power Rule: log(n^k) is O(log(n)) for any constant k > 0.
September 21st, 2008, 07:06 AM   #6
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Big Oh Notations Help

Quote:
 Originally Posted by animedear I was wondering how would you go about doing it with the Log of a Power Rule: log(n^k) is O(log(n)) for any constant k > 0.
I don't know what you mean by this.

And I don't use these rules you use (Transitive Rule, Power Rule), I just use the definition of Big O. log(n^k) = klog(n), and since the O is insensitive to multiplication by a constant, O(log(n^k)) = O(log(n)).

 Tags big, notations

,
,
,

,

,

,

# transiyivity rule in asymptotic notation

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Robert Lownds Real Analysis 1 June 8th, 2013 11:37 AM mathbalarka New Users 10 May 15th, 2013 08:22 AM antonvaset Algebra 1 June 2nd, 2012 08:03 AM sallyyy Algebra 4 June 30th, 2011 05:34 PM johnny Algebra 1 August 18th, 2007 02:37 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top