2

I recently solved a problem presented on https://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/

The problem is determining if a particular string can be represented from a substring by iterating the substring n times.

For example the string "abcabcabc" can be represented by iterating the substring "abc" 3.

I came up with this Java solution

public static boolean canForm (String str) {

    if(str.isEmpty()||str.length()==1) return true;

    int end;

    if (str.length()%2==0) {
        end = str.length()/2;
    } else {
        end = (str.length()-1)/2;
    }

    for (int i=1; i<=end; i++) {
        String s = str.substring(0,i);
        String compare = "";
        while (compare.length()<str.length()) {
         compare += s;
        }
        if (compare.equals(str)) return true;
    }

    return false;
}

One condition of the problem is for the solution to be O(n). I concluded it was O(n) but I am unsure if my solution really is O(n) or it is in fact O(n^2) and why.

tobias_k
  • 81,265
  • 12
  • 120
  • 179
CoderInLearning
  • 21
  • 1
  • 1
    If you could explain how you conclude its O(n), it would be better for you to correct you if mistaken rather than answering the question completely. – Shashwat Kumar Jan 22 '18 at 16:58
  • For each iteration, the string variable "compare" is is partly constructed by a substring of size str.substring(0,i). For example the string "abcd" will take 4 + 2 = 6 steps to be constructed. If we double the size of the string to "abcdefghi, it will be 8 + 4 + 3 + 2 steps. So the total number of steps will be some constant times n minus another constant so c*n - k for example. Thus the time complexity would be O(n). I want to know if this thinking is faulty so that it can be corrected and prevent me from making this mistake in the future. – CoderInLearning Jan 22 '18 at 17:02
  • 1
    Note that `for(...) { ... str.substring(...) ... }` alone already yields `O(n^2)` due to `substring` running in `O(n)`. Therefore see [Time complexity of Java's substring()](https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring). The same holds for concatenation `compare += s` and `compare.equals(str)`. All those sub-expressions run in `O(n)` and together with the wrapping `for`-loop it yields `O(n^2)`. – Zabuzard Jan 22 '18 at 17:07
  • Not an answer, but you can improve this by first checking whether `i` is a divisor of `str.length` – tobias_k Jan 22 '18 at 17:07
  • That is an idea I had in mind. I also have an alternative solution in mind that involves rotating the string and comparing the rotated string to the original string. If they are the same, then the string can be represented by a substring n times. I also have a Python solution in mind that takes advantage of the multiplicaton operator that can be used on strings. I just wanted to determine the time complexity of the solution I posted for learning purposes. – CoderInLearning Jan 22 '18 at 17:15
  • Thanks for the link Dukeling. I already know the general fundamentals of big o analysis I just sometimes have trouble applying them. – CoderInLearning Jan 22 '18 at 17:21
  • Thanks for the response Zabuza. I was unaware that str.substring now runs in O(n). I assumed it was O(1). I also assumed that str.equals(another string) was O(n). I assumed it was O(1) as well. – CoderInLearning Jan 22 '18 at 17:25
  • The time complexity of this might not necessarily be that simple to calculate, but that's mostly due to `compare += s;` (since that does O(i+2i+...+n) work for each i, at least if not optimised), which can easily be improved to use `StringBuilder` instead, at which point it becomes a fairly standard double for-loop. – Bernhard Barker Jan 22 '18 at 17:33
  • Seems one application of KMP algorithm. Find longest matching border of length which is factor of total length of the string. – Shashwat Kumar Jan 22 '18 at 18:11

1 Answers1

0

Your program runs in O(n^2), where n is propotional to the length of the string. Your code has a while loops that iterates n times in a for loop that iterates n times. Hence the order of the program is O(n*n)=O(n^2).

cdaiga
  • 4,861
  • 3
  • 22
  • 42
  • You may improve by adding non-trivial method calls to your analysis, like `substring` and the concatenation `compare += 2`. – Zabuzard Jan 22 '18 at 17:04
  • This is where I became confused. I understand it will iterate n times for the first iteration, but the number of iterations decrease for each iteration. So "abcdefghi" would be n + n/2 + 3 + n/4. It doesn't iterate n times for each iteration. It iterates n times for the first iteration and n/(some constant) for each iteration onwards. This is why I am confused. – CoderInLearning Jan 22 '18 at 17:12
  • @CoderInLearning you should know that O(an) where a is a constant is the same as O(n). – cdaiga Jan 22 '18 at 17:27
  • @cdaiga I know about the fundamentals of big O. Just as O(n^2 + n + 1) would be O(n^2) or O(48n^3 + 6n^2 + 1) would be O(n^3). Thank you for your help as each term in the sum is O(n). Whether it would be n/2 or n/4, each term evaluates to O(n). Over n times this would evaluate to O(n^2). So it would in fact evaluate to O(n^2). – CoderInLearning Jan 22 '18 at 17:30