0
$\begingroup$

There is a method that I want to calculate its complexity in asymptotic notation. It calls additional methods(equals and substring) which complexity is $O(n)$. If it was $O(1)$, I could figure out complexity of the calling method. I have tried some operations; however, I'm stuck on calculation with the additional part. Can you solve its complexity with steps?

public static int func(String x)
   if(x == null || x.equals(""))
      return 0;
   else
      return 1 + func(x.substring(1));

enter image description here

$\endgroup$
  • $\begingroup$ What is $n$? is it the length of the input x? If so, the running time depends on aFunctionWhichComplexityisO(n). In particular, we need to know what the length of its output will be. Also, does that function take x` as an input? If so, how does the length of its output depend on the length of x? $\endgroup$ – D.W. Mar 4 '17 at 20:59
  • $\begingroup$ the function is substring of Java. But what about equals? $\endgroup$ – itsnotmyrealname Mar 4 '17 at 23:09
  • $\begingroup$ Please edit the question to incorporate feedback from the comments. Don't just put clarifications in the comments -- we want questions to be self-contained and stand on their own. Thank you. $\endgroup$ – D.W. Mar 5 '17 at 2:54
  • $\begingroup$ I have edited. Thanks for your interest. @D.W. $\endgroup$ – itsnotmyrealname Mar 5 '17 at 6:31
1
$\begingroup$

This all comes down to the time it takes to compute x.substring(1) and x.equals("").

If these methods were implemented in the obvious way (x.substring(1) builds up a new string by copying characters; x.equals("") compares character-by-character until the first match), then x.substring(1) would take $O(n)$ time and x.equals("") would take $O(1)$ time (because it only looks at the first character of x; if that is non-empty, it returns false).

So let's calculate the running time under the assumption that these methods are implemented in the obvious, naive way. x.substring(1) returns a string of length $n-1$. Therefore, you recursively invoke func() on a string of length $n-1$. Let $T(n)$ denote the running time of func(x) when passed a string x of length $n$. We obtain the recurrence relation

$$T(n) = T(n-1) + O(n).$$

(In other words, the recurrence you had is correct.) This recurrence solves to

$$T(n) = O(n^2);$$

see https://cs.stackexchange.com/a/2803/755 for details how. So, if those were the right assumptions about the running time of substring() and equals(), the running time of your method would be $O(n^2)$.

However, it turns out that some versions of Java implement substring() in a particularly clever way, with the result that x.substring(1) takes only $O(1)$ time, not $O(n)$ time. In particular, x.substring(1) doesn't make any copies of the string. Instead, it creates a new string object (call it y) which has a pointer to x and effectively says "hey, this string skips the first character of x and starts at index 1".

Consequently, when you take into account this more sophisticated understanding of how substring() works in some versions of Java, the recurrence becomes

$$T(n) = T(n-1) + O(1).$$

That solves to $T(n) = O(n)$. So, the total running time of your code is actually only $O(n)$, in those versions of Java, due to the clever way that Java implements the substring() method.

See https://stackoverflow.com/q/4679746/781723 to learn more about the running time of substring() and which of these analyses applies to you.

$\endgroup$
  • $\begingroup$ Thank you for your illuminating answer because you have already explained the complexity difference among pre-java7 and java7-8. However, Java writers have changed its implementation due to preventing memory leak as far as I read. Jon Skeet's answer is on: stackoverflow.com/a/4679775 $\endgroup$ – itsnotmyrealname Mar 6 '17 at 8:18
1
$\begingroup$

The question is absolutely not answerable without knowing what aFunctionWhichComplexityisO(n) returns.

Assuming that the function takes x as an argument, it might for example check if x contains the decimal representation of an integer y, and returns a string with the decimal representation of y-1 if y > 0, and null if y ≤ 0 or x does not contain the decimal representation of an integer.

In that case if x contains n characters, the time is $O (n·10^n)$.

Or the function always returns null, then the time is $O (n)$.

$\endgroup$
  • 1
    $\begingroup$ The function can't be just "substring of Java". Substring has more than one argument. Substring with what arguments? Update your question with the information. And Swift substrings are often constant time. $\endgroup$ – gnasher729 Mar 4 '17 at 23:41
1
$\begingroup$

Assuming that you have the right recurrence:

$T(n)=T(n-1)+2+(n-1)$

then you have

\begin{align*} T(n)&=T(n-1)+2+(n-1)\\ T(n-1)&=T(n-2)+2+(n-2)\\ \vdots&=\vdots\\ T(n-k)&=T(n-k)+2+(n-k)\\ \vdots&=\vdots\\ T(1)&=T(0)+2+(1)\\ \end{align*}

Summing-up you obtain:

$T(n)=T(0)+2n+\sum_{i=1}^{n-1}i=2n+\frac{n(n-1)}{2}=\frac{n(n+3)}{2}$

(recall that $T(0)=0$)

Hope this is what you expected.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.