My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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?
gear2d is offline  
 
September 19th, 2008, 05:54 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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)
CRGreathouse is offline  
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?
gear2d is offline  
September 19th, 2008, 01:10 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
animedear is offline  
September 21st, 2008, 08:06 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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)).
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
big, notations



Search tags for this page
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





Copyright © 2019 My Math Forum. All rights reserved.