19

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);
aretai
  • 1,619
  • 6
  • 19
  • 30
  • "Time Complexity" usually means worst case time complexity. This problem has been proven impossible. – emory Mar 31 '12 at 18:34
  • I meant (big-O) complexity. Will edit the post as well. – aretai Mar 31 '12 at 18:38
  • If you want to count distinct digits in a number, that code definitely isn't an optimal solution both in time and space. – Philipp Reichart Mar 31 '12 at 18:46
  • how would you improve it Philipp? What places should be corrected? – aretai Mar 31 '12 at 18:50
  • There's no specific places, it's the whole approach: There's no need for strings, regular expressions and sets. Just some arithmetic (mod, div) and a single loop. The result would run in O(n) time and O(1) space, with n = number of digits in the input. Give me some minutes for the code. – Philipp Reichart Mar 31 '12 at 18:56
  • 1
    @PhilippReichart: also the intent would be more obvious(!) – Kevin Mar 31 '12 at 18:58

2 Answers2

19

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.

wjandrea
  • 28,235
  • 9
  • 60
  • 81
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • You said that there are tools to measure complexity by running it with different inputs. How is that different from if a user himself runs his code with different inputs and calculates the time. Will both give the same results ? Automatic vs Manual ? – Faizan Mar 03 '13 at 21:04
  • @Faizan- The tool does a lot more than just run the program. It adds a lot of binary instrumentation to measure individual functions / blocks of code, and it's certainly a lot easier than doing it by hand. In principle you could do the same thing manually, but it would be *much* harder. – templatetypedef Mar 03 '13 at 22:31
  • @templatetypedef it's always beneficial if you provide the name of the paper and not just "in this paper" as links broke quite often. – Vishrant Jan 17 '18 at 01:51
4

I might be solving someone's homework, but the question was begging for a sane solution...

Counting distinct digits in a number requires no strings, sets or regular expressions, just some simple arithmetics.

The following method runs in O(n) time (n = number of digits in the input) and constant space:

int distinctDigits(int num) {
  if (num == 0) {
    return 1;
  }

  boolean[] digits = new boolean[10];

  while (num > 0) {
    digits[num % 10] = true;
    num /= 10;
  }

  int count = 0;
  for (boolean digit : digits) {
    if (digit) {
      count++;
    }
  }

  return count;
}

Making this work for negative numbers is left as an exericse to the reader ;)

Philipp Reichart
  • 20,771
  • 6
  • 58
  • 65
  • nah it wasn't my homework thank you. Actually I thought about this approach as well; however thought that converting to String and then using Set would be more efficent (time complexity). – aretai Mar 31 '12 at 19:12
  • yes it is a neat solution as well thank you. Although it doesn't directly answer my question (as the one above) but 1 upvote you have. – aretai Mar 31 '12 at 19:15
  • I am afraid that your solution is not that neat as I thought try checking this 000121212 as input it will produce a value of 4. My code also fails this test. – aretai Mar 31 '12 at 19:29
  • 3
    `0121212` is interpreted as octal number (leading zero) and is `41610` as a decimal number and therefore 4 is correct. – zapl Mar 31 '12 at 19:49
  • yes you are right thought that there was some conversion in the back – aretai Mar 31 '12 at 19:55