What is the Big O notation of a program?

Question

I am trying to determine the algorithmic complexity of this program:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class SuffixArray
{
    private String[] text;
    private int length;
    private int[] index;
    private String[] suffix;
 
    public SuffixArray(String text)
    {
        this.text = new String[text.length()]; 
 
        for (int i = 0; i < text.length(); i++)
        {
            this.text[i] = text.substring(i, i+1);
        } 
 
        this.length = text.length();
        this.index = new int[length];
        for (int i = 0; i < length; i++)
        {
            index[i] = i;
        } 
 
        suffix = new String[length];
    }
 
    public void createSuffixArray()
    {   
        for(int index = 0; index < length; index++) 
        {
            String text = "";
            for (int text_index = index; text_index < length; text_index++)
            {
                text+=this.text[text_index];
            } 
            suffix[index] = text;
        }
 
        int back;
        for (int iteration = 1; iteration < length; iteration++)
        {
            String key = suffix[iteration];
            int keyindex = index[iteration];
 
            for (back = iteration - 1; back >= 0; back--)
            {
                if (suffix[back].compareTo(key) > 0)
                {
                    suffix[back + 1] = suffix[back];
                    index[back + 1] = index[back];
                }
                else
                {
                    break;
                }
            }
            suffix[ back + 1 ] = key;
            index[back + 1 ] = keyindex;
        }
 
        System.out.println("SUFFIX \t INDEX");
        for (int iterate = 0; iterate < length; iterate++)
        {  
            System.out.println(suffix[iterate] + "\t" + index[iterate]);
        }
    }
 
 
    public static void main(String...arg)throws IOException
    {
        String text = "";
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the Text String ");
        text = reader.readLine();
 
        SuffixArray suffixarray = new SuffixArray(text);
        suffixarray.createSuffixArray();
    } 
}

I have done some research on Wikipedia about the Big-O notation and have run the code with strings of different sizes. Based on the time it takes to run the code with different-size stings, I feel its complexity might be O(n^2). How can I know for sure?

Any help would be greatly appreciated.

Answer 1

The complexity of your createSuffixArray method is O(n^2) and you can determine that by examining the 3 looping blocks. Also, since in your question you said you've read the Wikipedia article covering the Big-O notation, then focus on its properties. They are the core of how to apply the right logic and compute the complexity of an algorithm.

Within your first block, the innermost loop iterating length times is in turn repeated for length times, yielding a complexity of O(n^2) due to the Product Property of the Big-O notation.

for(int index = 0; index < length; index++) 
{
    String text = "";
    for (int text_index = index; text_index < length; text_index++)
    {
        text+=this.text[text_index];
    } 
    suffix[index] = text;
}

In your second block, although the innermost loop does not perform length iterations at the beginning, its complexity still tends to O(n), producing again an overall complexity of O(n^2) due to the Product Property.

for (int iteration = 1; iteration < length; iteration++)
{
    String key = suffix[iteration];
    int keyindex = index[iteration];

    for (back = iteration - 1; back >= 0; back--)
    {
        if (suffix[back].compareTo(key) > 0)
        {
            suffix[back + 1] = suffix[back];
            index[back + 1] = index[back];
        }
        else
        {
            break;
        }
    }
    suffix[ back + 1 ] = key;
    index[back + 1 ] = keyindex;
}

Your third and last block simply iterates length times, giving us a linear complexity of O(n).

for (int iterate = 0; iterate < length; iterate++)
{  
    System.out.println(suffix[iterate] + "\t" + index[iterate]);
}

At this point to get the method complexity, we need to gather the 3 sub-complexities we've got and apply to them the Sum Property, which will yield O(n^2).