My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
March 29th, 2013, 12:34 AM   #1
Member
 
Joined: Mar 2013

Posts: 66
Thanks: 0

Computational Complexity

How do you determine the best "big-Oh" form?

Use the results of Table 1 to determine the best “big-Oh” form for the following function f: Z^+? R.
f(n) = 3n + 7

Table 1 (I'm not sure how to write tables so I used the dash (-----):


Big-Oh Form ------------------------ Name
O(1) --------------------------------- Constant
O(log_2 n) -------------------------- Logarithmic
O(n) --------------------------------- Linear
O(n log_2 n) ------------------------ n log_2 n
O(n^2) ------------------------------ Quadratic
O(n^3) ------------------------------ Cubic
O(n^m), m = 0, 1, 2, 3,... ------- Polynomial
O(c^n), c > 1 ----------------------- Exponential
O(n!) -------------------------------- Factorial
rhymin is offline  
 
March 29th, 2013, 06:17 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: Computational Complexity

The table is arranged in order. If O(g(n)) is followed by O(h(n)) and your function is O(g(n)) but not O(h(n)) you're done and the answer is O(g(n)).

You could start at the middle of the table and use binary search. Is your function in O(n^2)? If so, next check if the function is in O(n); if not, check if it is in O(n^m) for some m.
CRGreathouse is offline  
March 29th, 2013, 03:43 PM   #3
Member
 
Joined: Mar 2013

Posts: 66
Thanks: 0

Re: Computational Complexity

Thank you.

How would you apply f(n) = 3n + 7 to this?
rhymin is offline  
March 29th, 2013, 04:39 PM   #4
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: Computational Complexity

I would start by testing if it is O(n^2). Do you know how to do that? What is the definition of O(n^2)?
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
complexity, computational



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
The computational complexity of calculation function Wilhelm12 Computer Science 1 May 29th, 2013 09:18 AM
Special Functions and Computational Complexity rhymin Applied Math 3 April 2nd, 2013 05:53 AM
Computational complexity of incremental standard deviation murad Advanced Statistics 0 January 21st, 2013 05:07 AM
Computational Mathemtics MyNameIsVu Computer Science 2 April 13th, 2009 11:04 AM
Computational Mathematics Infinity Computer Science 2 March 18th, 2007 09:18 PM





Copyright © 2017 My Math Forum. All rights reserved.