My Math Forum Computational Complexity

 Computer Science Computer Science Forum

 March 28th, 2013, 11:34 PM #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
 March 29th, 2013, 05: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, 02: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, 03: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)?

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Wilhelm12 Computer Science 1 May 29th, 2013 08:18 AM rhymin Applied Math 3 April 2nd, 2013 04:53 AM murad Advanced Statistics 0 January 21st, 2013 04:07 AM MyNameIsVu Computer Science 2 April 13th, 2009 10:04 AM Infinity Computer Science 2 March 18th, 2007 08:18 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top