3

I am trying to get an algorithm down to at least O(n^(3/2)) complexity. Here is the algorithm:

function( string s, int n )
{
    bool result = false;
    int position = 0;
    for( int i = 0; i < n/2; i++ )
    {
        position = 0;
        for( int j = i+1; j < n; j++ )
        {
            if( s[j] != s[position] ) break;        
            if( j == n ) result = true;
            if( position == i ) position = 0;
            else position++;        
        }
        if(result) break;       
    }
    return result;
}

The first for-loop will iterate n/2 times, which is O(n) complexity. I need to get the inside for-loop to be at most O(sqrt(n)), thus giving the entire algorithm a O(n^(3/2)) complexity. I am having difficulty trying to figure out if the nested for loop is the right complexity I need.

Note:
n is the size of the string. The function basically checks to see if a repeating pattern occurs in the string s. The only characters in s are "0" and "1". For example, if the string is "001001", then the pattern is "001" and occurs twice. The string is also even. That being said, syntax and functionally are irrelevant for this question. All basic actions are considered to take O(1) (constant) time, which is pretty much the entirety of this code.

Note2:
I am doing this for homework. But the homework question was just to get the algorithm working, which I have done. Getting the complexity down is just extra work to practise.

Any help or guidance would be appreciated!

Improve this question
7
  • What the algorithm does? Commented May 17, 2012 at 2:19
  • I explained this in the "Note:" under the code. It determines if the string s is comprised of a repeating pattern. For example, "001001" is made up of "001" twice. "000000" is made up "0" 6 times. "010100" would be an example of one that isn't made up of a pattern. Commented May 17, 2012 at 2:34
  • This is an O(N) job. You need a slightly modified string search algorithm. Commented May 17, 2012 at 5:18
  • 2
    I mean, an O(N) string search algo like Knuth-Morris-Pratt. Commented May 17, 2012 at 5:41
  • 1
    @svinja: This is called "finding the period of a string". An easy way to find one is to search for a string within a square of itself (with the first and the last characters chopped off, to eliminate the trivial cases). There's an article (pdf) that discusses algorithms with better average running time. Commented May 17, 2012 at 13:47

2 Answers 2

Reset to default
2

It is very easy, simply check whether the length divides the total length (it has to, a string can't be a repeating pattern of length L if L doesn't divide the total length) and don't run the inner loop if it doesn't... Upper bound of number of divisors is 2sqrt(n) so this guarantees O(Nsqrt(N)).

If you're wondering why, the maximum number of divisors a number could have is every number up to sqrt(n), and then for each of those numbers x, N/x. So under 2sqrt(N).

Of course, numbers have a lot less divisors in reality, except for 12 which actually has all of them: 1,2,3 (every number up to sqrt), 12/1, 12/2, 12/3 (inverses).

There are 2 inner loops but one runs L times and the other one N/L times so the inner loops are O(N).

    static bool f(string s)
    {
        int n = s.Length;
        for (int l = n / 2; l >= 1; l--)
        {
            if (n % l != 0) continue;
            bool d = true;
            for (int o = 0; o < l; o++)
            {
                char f = s[o];
                for (int p = l; p < n; p += l)
                    if (s[p + o] != f) d = false;
            }
            if (d == true) return true;
        }
        return false;
    }

The key line is:

if (n % l != 0) continue;

otherwise it would be O(N^2).

While the outer loop may seem to be N/2 at first glance, it is mathematically guaranteed to be < 2sqrt(N). Which you can also see by running it on a string of a few million characters - it will work quickly.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Oh, that makes a lot of sense. I confused myself with how complex my inner loop was. Thanks a lot, that cleared up a few things!
0

I think that your inner loop cant be brought down to O(sqrt(n)) as you have to compare all characters from start of string to those from a specific index i whose value is governed by outer loop.

Improve this answer

1 Comment

It says the overall algorithm can be done in O(n^3/2) complexity. I figured the outside loop must be O(n) and then the inside O(sqrt(n)), and that is the way I designed it. Should it perhaps be flipped?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.