LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 10-04-2010, 08:21 PM   #1
jfhebb
LQ Newbie
 
Registered: Oct 2010
Posts: 1

Rep: Reputation: 0
Big-O and Big-Omega Problem


So, I have a problem to show an example of a positive function f(n) so f(n) is neither O(n) or Ω(n). Any help?
 
Old 10-04-2010, 11:01 PM   #2
dugan
Senior Member
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 4,678

Rep: Reputation: 1441Reputation: 1441Reputation: 1441Reputation: 1441Reputation: 1441Reputation: 1441Reputation: 1441Reputation: 1441Reputation: 1441Reputation: 1441
I started writing an example (because this is an exceptionally easy question), but I thought better of it: doing your homework for you isn't right.

Hint: it's really easy to come up with a function involving nested loops where the best case and the worst case are both n-squared.

Last edited by dugan; 10-04-2010 at 11:03 PM.
 
Old 10-04-2010, 11:04 PM   #3
Berhanie
Senior Member
 
Registered: Dec 2003
Location: phnom penh
Distribution: Fedora
Posts: 1,625

Rep: Reputation: 165Reputation: 165
without getting into details, the idea is this: start with f which is not O(n), and g which is not Ω(n).
use those two functions to define another function h which is guaranteed to be neither O(n) nor Ω(n).
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Big O, Big Omega, and Big Theta oulevon Programming 7 05-26-2010 07:18 AM
[acer Extensa 5620Z] I got a big big problem, please help ^^ VodkaRocks Linux - Wireless Networking 11 06-26-2009 07:08 AM
LXer: Why Big Compute and Big Storage will meet Big Pipe at the Last Mile LXer Syndicated Linux News 0 12-23-2007 01:20 PM
BIG BIG PROBLEM with nvidia driver for linux x86 basshead62887 Linux - Hardware 5 09-12-2007 12:33 AM
Installing RH 9 with RAID 5 --Big, big Problem!!! rhonneil Linux - Software 2 09-25-2003 08:13 PM


All times are GMT -5. The time now is 05:56 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration