User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      