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() 
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() } 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 worstcase, no. You can use it for average case, amortized analysis, etc. It's usually introduced on worstcase 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:
 
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:
 

Tags 
big, notation 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

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