Menu
I have a question regarding time complexity (big O notation) for Java software. Is there a way to quickly calculate or test it (or any website that could calculate it for me would be welcomed). For example I would like to check it for the following snippet of code and possibly improve as well:
int dcount = 24423567;
int a = 0;
if (dcount == 0){
a = 1;
}
String ds = Integer.toString(dcount);
String[] sa = ds.split("(?<=.)");
HashSet hs = new HashSet();
Collections.addAll(hs, sa);
a = hs.size();
if (dcount < 0)
a--;
System.out.println(a);
754
Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound) Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound) Finally, Big Θ describes the set of all algorithms that run at a certain speed (it's like equality)
The time complexity of a loop is equal to the number of times the innermost statement is to be executed. On the first iteration of i=0, the inner loop executes 0 times. On the first iteration of i=1, the inner loop executes 1 times. On the first iteration of i=n-1, the inner loop executes n-1 times.
Big-O notation counts how many steps an algorithm must execute to gauge its efficiency. Approaching your code in this manner can be very effective if you need to tune your code to increase efficiency.
As @emory pointed out, it is provably impossible to determine the big-O time complexity of an arbitrary piece of code automatically (the proof is a reduction from the halting problem). However, there are tools that can attempt to measure the complexity of a piece of code empirically by running it on several different inputs. One such tool is described in the paper “Measuring Empirical Computational Complexity” by Goldsmith, Aiken, and Wilkerson. It works by attempting to do a regression on the program's runtime versus its input size. The tool, called trend-prof, has been discontinued, but is archived here for reference.
86
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
