CODEWITHSUNDEEP
algorithmperformancebig-o
CJR
CJR

Reputation: 3572

Time complexity of this algorithm? (Big O)

I am trying to figure out the time complexity of this code, as a part of my assignment. Here is how the code looks like:

public int solvePuzzle( )
{
    searchAlg = BINARY_SEARCH ? new BinarySearch() : new LinearSearch();
    int matches = 0;
    for( int r = 0; r < rows; r++ )
        for( int c = 0; c < columns; c++ )
            for( int rd = -1; rd <= 1; rd++ )
                for( int cd = -1; cd <= 1; cd++ )
                    if( rd != 0 || cd != 0 )
                        matches += solveDirection( r, c, rd, cd );
    searchAlg.printStatistics();
    return matches;
}

This method either uses a Binary Search or Linear Search.

My assignment ask me to find the time complexity of this in T(M,N) = O(?) where M is the size of a sorted dictionary which will be search using either linear of binary search, and N is the size of the "puzzle" (char [][]) where both array(Rows and Columns = N = same size).

This part matches += solveDirection( r, c, rd, cd ); uses either binary/linear search to search through a sorted array.

So far, this is what I've come up with.

The Time complexity of Binary search is Log M The Time complexity of Linear Seach is M

The Time complexity of the first two for-loop's are N each.

But what is the Time complexity of the 3rd and 4th loop, and what is T(M,N) equal to?

Is it O(3) for the 3r of 4th loop? Does it mean that T(M,N) = O(M * N * N * 3 * 3)/O(logM * N * N * 3 * 3) ?

Any help would de appreciated.

EDIT: the code for solveDirection():

private int solveDirection( int baseRow, int baseCol, int rowDelta, int colDelta )
{
    String charSequence = "";
    int numMatches = 0;
    int searchResult;

    charSequence += theBoard[ baseRow ][ baseCol ];

    for( int i = baseRow + rowDelta, j = baseCol + colDelta;
             i >= 0 && j >= 0 && i < rows && j < columns;
             i += rowDelta, j += colDelta )
    {
        charSequence += theBoard[ i ][ j ];
        if ( charSequence.length() > maxWordLength )
            break;

        searchResult = searchAlg.search( theWords, charSequence );

        if( searchResult == theWords.length ) {   // corrected by UH 2007-05-02
            // either linear searched failed or binary search failed because charSequence
            // is larger than the largest word in theWords
            if ( searchAlg instanceof BinarySearch )
                break;    // binary search failed and it makes no sense to extend charSequence any further
            else
                continue; // linear search failed but an extension of charSequence may succeed
        }

        // precondition: 0 <= searchResult < theWords.length
        // At this point one, and only one, of three conditions holds:
        // 1. Linear search succeeded
        // 2. Binary search succeded
        // 3. Binary search failed at the insertion point for charSequence, 
        //    which means that theWords[ searchResult ] is the least element greater than charSequence

        if( PREFIX_TESTING && ! theWords[ searchResult ].startsWith( charSequence ) )
            break;

        if( theWords[ searchResult ].equals( charSequence ) ) {
//              if( theWords[ searchResult ].length( ) < 2 )
//                  continue;
            numMatches++;
            if ( PRINT_WORDS ) 
                System.out.println( "Found " + charSequence + " at " +
                        baseRow + " " + baseCol + " to " + i + " " + j );
        }
    }

    return numMatches;
}

Upvotes: 0

Views: 189

Answers (1)

Konrad Rudolph
Konrad Rudolph

Reputation: 545518

You’re on the right track.

However, the key insight is that O(k) = O(1) for any constant k (= independent of the size of the input). As such, your O(N·N·3·3) is the same as O(N·N). And this result needs to be multiplied with the search, which you’ve done correctly.

Upvotes: 2

Related Questions