1

Possible Duplicate:
Big O, how do you calculate/approximate it?
Plain English explanation of Big O

I just saw this question: Find nearest number in unordered array. In answers peoples are talking about complexity of approach they are proposing. How do they calculate it? What does O(n) or O(logn) means? How to find/Calculate complexity of a method/program?

Community
  • 1
  • 1
Harry Joy
  • 58,650
  • 30
  • 162
  • 207
  • 6
    http://en.wikipedia.org/wiki/Big_O_notation – JB Nizet Jan 31 '12 at 09:00
  • 2
    See: [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) and [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it). – Sebastian Paaske Tørholm Jan 31 '12 at 09:02
  • You can calculate it by knowing how it is implemented, you can estimated it empirically and you can test how your application works with realistic data and you can get different outcomes. Big-O is a way of compare algorithms complexity as the amount of work increases. It is useful to understand Big O, but you should also be aware that it doesn't tell you the whole story. – Peter Lawrey Jan 31 '12 at 09:03
  • this may help you http://leepoint.net/notes-java/principles_and_practices/complexity/complexity_measurement.html – Hemant Metalia Jan 31 '12 at 09:03
  • +1. I cannot agree with punishing for asking prog questions on the site for asking prog questions. – Gangnus Jan 31 '12 at 09:19

3 Answers3

2

Complexity has sense when your algorithm works with n similar elements. And says, how the time changes according to changes of n. So, if n rises 2 times and the time raises 2 times, you have O(n) complexity.

If the time raises as (n^2+2000n) function, we also say that the complexity is again O(n^2). The theory thinks only on greater values of n, greater than any other constants in your algorithm. So, the theory does not always fits your need, beware that. It is not the problem of the theory of algorithms, it is problem of its application that often doesn't pay attention to the important details

How you can guess? Well, if you are doing the same operation n times, where n is the number of array elements, you have O(n). If you are doing the same operation first n times, than n-1 times, than n-2 and down to 1, you have complexity n+(n-1)+...+1. It is n(n+1)/2, that is again const*n+const2*n^2. So, it is O(n^2). When n will be large enough, twice n will mean 4 time the time. Logics and arithmetics.

Gangnus
  • 24,044
  • 16
  • 90
  • 149
1

Short answer: O(), o(), etc... are notations describing the trend at which a function will grow, depending of its variables. e.g. f(x) = x^2 + x - 6 => O(x^2) because the growth is driven by the highest polynomial degree in the function. More on this specific topic: Big O notation

Long answer: those notations are the very basis of the study of algorithms and computation theory. you might want to read a nice book about it. One of the most famous books on Algorithms out there

Also, OpenMIT has the whole course available for free. It's very interesting!.

mdm
  • 3,928
  • 3
  • 27
  • 43
0

That is known and Big O Notation and is used to find the Computational Time Complexity of a given algorithm. You can find a short guide on how to calculate it for yourself here. Although it is not Java, the concept of what time complexity is, is language agnostic so you should be fine. However note that method with similar names can have different time complexities accross different languages.

npinti
  • 51,780
  • 5
  • 72
  • 96