I really can't figure out what "Big-O" is and how to use it in practice, so I hope someone could give me a simple explanation and maybe a little programming example in Java.
I have the following questions:
What does these terms mean (as simple as possible) and how is it used in java: BigO(1), BigO(n), BigO(n2) and BigO(log(n)) ?
How do you calculate a Big-O from an existing java code?
How do you use Big-O sorting
How do you use Big-O recursion
I hope someone will be able to help.
Big O is used to give an idea of how fast an algorithm will scale as input size increases
O(1) means that as input size increases, the running time will not change
O(n) means that as input size doubles, the running time will double, more or less
O(n^2) means that as input size double, the running time will quadruple, more or less
O(f(n)) means that as input size doubles, the running time will increase to around f(2n)
Regarding Big-O, sorting, and recursion.
Big-O sorting isn't really an algorithm. You can however use Big O to tell you how fast your sorting algorithm is.
For computing Big-O of a recursive function, I would recommend using the Master Theorem.
Guidelines for determining Big O:
Usually, you need to determine what your input size is (like array length, or number of nodes in your linked list, etc)
Then ask yourself, what happens if your input size doubles? Or triples? If you have a for loop that goes through each element:
//say array a has n elements
for (int i = 0; i < n; i++) {
// do stuff
a[i] = 3;
}
Then doubling n would make the loop run twice as long, so it would be O(n). Tripling n would triple the time it takes, so the code scales linearly with the input size.
If you have a 2D array and nested for loops:
// we say that each dimension of the array is upper bounded by n,
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// do stuff
a[i][j] = 7;
}
}
As n doubles, the code will take 2^2 = 4 times as long. If input size triples, code will take 3^2 = 9 times as long. So Big O is O(n^2).