
Computer Science Computer Science Forum 
 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 "bigOh" form? Use the results of Table 1 to determine the best “bigOh” 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 (): BigOh 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 
March 29th, 2013, 06:17 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: 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. 
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? 
March 29th, 2013, 04:39 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: 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)?


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 