September 18th, 2008, 04: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, 05: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:
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, 12:28 PM  #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, 01: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:
 
September 20th, 2008, 09: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, 08: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:
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 
Search tags for this page 
big o notation transitivity proof,transitivity big oh notation,big oh rule of transitivity,is big oh notation is transitive,is big oh notation transitive? in algorithm,prove transitivity of bigoh notation,transiyivity rule in asymptotic notation
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Notations of (partial) derivatives  Robert Lownds  Real Analysis  1  June 8th, 2013 12:37 PM 
Notations for tetration  mathbalarka  New Users  10  May 15th, 2013 09:22 AM 
Math notations!? CONCEIVABLE  antonvaset  Algebra  1  June 2nd, 2012 09:03 AM 
Set notations  sallyyy  Algebra  4  June 30th, 2011 06:34 PM 
Sigma Notations  johnny  Algebra  1  August 18th, 2007 03:37 AM 