My Math Forum big O notation

 Computer Science Computer Science Forum

 July 15th, 2013, 10:27 AM #1 Senior Member   Joined: Mar 2012 From: Belgium Posts: 654 Thanks: 11 big O notation How to determine the complexity of any code ?
 July 15th, 2013, 10:40 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: big O notation It's not possible, in general, by Rice's theorem. In simple cases you can count the loops and multiply the number of elements in the loop. So Code: for n = 1 to log(x) for m = 1 to x something() takes x log x times as long as something().
 July 15th, 2013, 10:51 AM #3 Senior Member   Joined: Mar 2012 From: Belgium Posts: 654 Thanks: 11 Re: big O notation Okay Thank you. Code: try { for n = 1 to 10*log(x%4) for m = 1 to x something() } where the % is the mod operator I believe big O notation was also always counting the worst case scenario right ? so this would always be O(4x) even though there are cases where something() gets never executed and in some cases it gets executed 3x times. Am I right or not ? /:
 July 15th, 2013, 11:14 AM #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: big O notation In the worse case the code takes O(x). (The function runs at most 10 times, but O(10x) is the same as O(x) of course). Big O is not always used for worst-case, no. You can use it for average case, amortized analysis, etc. It's usually introduced on worst-case problems, though.
 July 15th, 2013, 11:24 AM #5 Senior Member   Joined: Mar 2012 From: Belgium Posts: 654 Thanks: 11 Re: big O notation Why is O(10x) the same as O(x) I'm sorry for the basic questions but I don't know much about this.
July 15th, 2013, 11:48 AM   #6
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: big O notation

Quote:
 Originally Posted by gelatine1 Why is O(10x) the same as O(x) I'm sorry for the basic questions but I don't know much about this.
What definition does your class use for big-O?

 July 15th, 2013, 11:57 AM #7 Senior Member   Joined: Mar 2012 From: Belgium Posts: 654 Thanks: 11 Re: big O notation Learning all by myself. I was thinking about an multiplication algorithm and I found one I think and I wanted to compare with other algorithms with big O notation. I was not sure how to do this so I came here to ask it.
 July 15th, 2013, 03:00 PM #8 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: big O notation OK, so what definition do you use?
 July 15th, 2013, 03:14 PM #9 Senior Member   Joined: Mar 2012 From: Belgium Posts: 654 Thanks: 11 Re: big O notation I use it like this: if you have an input of 5 in your program with coplexity O(n^2) The program then does 25 operations/loops to complete whatever you want to calculate. I use it as some indicitor how fast the algorithm works. It's not really a definition but that's how I think of it. EDIT not really input of 5 but for example a number from 5 ciphers. I usually write algorithms for operations on numbers.
July 15th, 2013, 03:22 PM   #10
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: big O notation

Quote:
 Originally Posted by gelatine1 I use it like this: if you have an input of 5 in your program with coplexity O(n^2) The program then does 25 operations/loops to complete whatever you want to calculate. I use it as some indicitor how fast the algorithm works.
That's not big O, that's instruction counting. If your program takes 25 steps to complete, say "25 steps to complete", not "O(25)".

 Tags big, notation

mod big o notation

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Alexis87 Algebra 1 April 3rd, 2013 08:08 AM ploktoc Number Theory 1 December 19th, 2012 04:49 PM Aqil Applied Math 3 November 25th, 2012 09:36 AM Christ1m Computer Science 13 April 17th, 2012 12:12 PM ElMarsh Linear Algebra 9 November 5th, 2009 01:35 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top