My Math Forum Big O complexity

 Computer Science Computer Science Forum

 August 31st, 2010, 02:55 AM #1 Member   Joined: Aug 2008 Posts: 44 Thanks: 0 Big O complexity Please, help me correct (if necessary) and complement my "solutions". Expressions can't be simplified, that is, you can not change $O(\log\frac{n^2}{m})$ into $O(2\log n - \log m)=O(\log n - \log m)$.$O(n^m)$ recursive Code: int RECURSION(int n, int m){ if (m > 1) { for (int i = 0; i < n; i++) { return RECURSION(n, m-1); } } [/*:m:3bzix122] $O(n^m)$ iterative (Should be done by using stack, but how exactly?) [/*:m:3bzix122] $O(n!)$ iterative Code: int counter = n; int factorial = 1; // Will store the final result n! while (counter > 1) { factorial *= counter--; } [/*:m:3bzix122] $O(n!)$ recursive Code: int RECURSION(int n) { int factorial; if (n > 1) return ( factorial * RECURSION(n-1) ); else return 1; } [/*:m:3bzix122] $O(\log\frac{n^2}{m})$ Code: for (int i = sqrt(n)/m; i > 0; i /= 10) // Assume 10-base logarithm. One "for" loop is not allowed, so how should above one-liner be rewritten?[/*:m:3bzix122]

 Tags big, complexity

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post rhymin Computer Science 3 March 29th, 2013 04:39 PM dwnielsen Number Theory 2 February 26th, 2013 09:19 PM stribor Computer Science 3 January 24th, 2013 12:32 AM ulita Computer Science 2 August 18th, 2010 07:56 AM UnOriginal Applied Math 2 August 26th, 2009 08:05 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top