My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
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 ?
gelatine1 is offline  
 
July 15th, 2013, 10:40 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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().
CRGreathouse is offline  
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 ? /:
gelatine1 is offline  
July 15th, 2013, 11:14 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
gelatine1 is offline  
July 15th, 2013, 11:48 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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?
CRGreathouse is offline  
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.
gelatine1 is offline  
July 15th, 2013, 03:00 PM   #8
Global Moderator
 
CRGreathouse's Avatar
 
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?
CRGreathouse is offline  
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.
gelatine1 is offline  
July 15th, 2013, 03:22 PM   #10
Global Moderator
 
CRGreathouse's Avatar
 
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)".
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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
big-o 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





Copyright © 2019 My Math Forum. All rights reserved.