CODEWITHSUNDEEP
algorithmtime-complexity
Praveen Pandey
Praveen Pandey

Reputation: 698

How to find the complexity of a program to find the length of the largest sub string?

I wrote a sample javascript program to find the length of the largest sub string of a given string and it works. I am not able to calculate its time complexity. Can someone help me? I do understand that a program with two loops is quadratic complexity, that with three loops has cubic complexity and so on. Is this always true? This program has two loops. Can I say that its complexity is O(n^2)?

function AllSubStrings()
{
    var myString = prompt("Enter the string");
    var arr = myString.split("");
    var tempArr = [];
    var maxLength = 0;

    for(var i = 0; i<arr.length; i++)
    {
        temp = null;

        for(var j = i; j<arr.length; j++)
        {
            if(j === i)
            {
                tempArr.push(arr[j])
                temp = arr[j];
            }
            else
            {
                temp = temp + arr[j];
                if(temp.length > maxLength)
                {
                    maxLength = temp.length;
                }
                tempArr.push(temp);
            }
        }
    }
    document.write("All SubStrings are: "+tempArr+"<br/>");
    document.write("Length of the largest substring is: "+maxLength);
}

Upvotes: 1

Views: 435

Answers (3)

kdurga
kdurga

Reputation: 97

Simple answer : As you have two nested loops each running in order of n, the total runtime is O(n*n).

Little more detailed one: first loop runs from 0 till n-1, second one runs from i till n-1. so for each i inner loop runs for n+n-1+n-2+...1 = n*(n+1)/2= O(n*n)

Upvotes: 0

Jayram
Jayram

Reputation: 19578

As you have two loops of order N, complexity is O(N2).

Upvotes: 1

Saeed Amiri
Saeed Amiri

Reputation: 22555

You have two nested loops of order n (where n is the length of string), so is O(n*n) = O(n2).

There are some other operations which are not important in calculating big O, e.g Split, takes O(n), but compare to O(n2) is not important, or push and pop, ... in each for loop takes O(1), but it's not important if we have multiple O(1) operations.

For elaboration: We know that the first loop runs n times, but about the second loop, it will run O(n-i) time, so total running time is:

Σ(n-i) = Σ n - Σ i = n2 - n(n-1)/2 = O(n^2).

Upvotes: 1

Related Questions