My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
August 17th, 2010, 12:26 AM   #1
Newbie
 
Joined: Aug 2010

Posts: 2
Thanks: 0

O(sin n), ?(sin n), ?(sin n) complexity

Hello , Do you know examples of functions belonging crowds O(sin (n)), ? (sin (n)), ? (sin (n)) ?
ulita is offline  
 
August 17th, 2010, 06:14 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: O(sin n), ?(sin n), ?(sin n) complexity

Quote:
Originally Posted by ulita
Hello , Do you know examples of functions belonging crowds O(sin (n)), ? (sin (n)), ? (sin (n)) ?
I suppose it depends on the exact definitions you use. I think of O(g(n)) as the set of functions f(n) such that there exists C with

or maybe the same but only for large enough N. So with either of those definitions, there are no functions in O(sin n), since sin n < 0 for arbitrarily large n.

Using the equivalent definition for ? with

it's easy to see that (among others) all functions bounded below by a positive constant are in ?(sin n).

The usual definition of ?(g(n)) is usually just the intersection of ?(g(n)) and O(g(n)), right? So in that case there would be no functions in ?(g(n)).


For weird cases like this, though, it's going to come down to the definitions. There are lots of definitions that are all the same for the usual functions, but differ on pathological examples.
CRGreathouse is offline  
August 18th, 2010, 07:56 AM   #3
Newbie
 
Joined: Aug 2010

Posts: 2
Thanks: 0

Re: O(sin n), ?(sin n), ?(sin n) complexity

Thanks a lot.
ulita is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
complexity, osin, sin



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
Computational Complexity rhymin Computer Science 3 March 29th, 2013 04:39 PM
Rhythmic complexity dwnielsen Number Theory 2 February 26th, 2013 09:19 PM
complexity of this function stribor Computer Science 3 January 24th, 2013 12:32 AM
Big O complexity courteous Computer Science 0 August 31st, 2010 02:55 AM
Complexity of Problem UnOriginal Applied Math 2 August 26th, 2009 08:05 AM





Copyright © 2017 My Math Forum. All rights reserved.