CODEWITHSUNDEEP
javaalgorithm
RusJaI
RusJaI

Reputation: 794

naive algorithm implementation

why can't the Naive algorithm have o(n) time complexity? This is my Java code which gave me the expected results.. Please explain what's wrong with this...

import java.util.*;
class NaiveAlgo{
    public static void main (String args[]){
        System.out.print("Enter the Text : ");
        Scanner inp1=new Scanner(System.in);
        String txt=inp1.nextLine();
        int lengthT=txt.length();

        System.out.print("Enter the Pattern : ");
        Scanner inp2=new Scanner(System.in);
        String ptn=inp2.nextLine();
        int lengthP=ptn.length();

        int i=0,j=0,index=0;

        while(j!=lengthP&& i!=lengthT){
            if(txt.charAt(i)==ptn.charAt(j)){
              i++;
              j++;
            }else{
              j=0;
              index++;
              i=index;
            }
        }

    if(index<lengthT)
            System.out.println("Index : "+index);
    else
            System.out.println("Not found ");
    }
}

Upvotes: 0

Views: 191

Answers (1)

Timothy T.
Timothy T.

Reputation: 1091

Your algorithm is not of O(n) complexity. It's not performing a linear search -- this happened when you reset j=0 and i=index when the characters don't match.

It won't be efficient with an exaggerated worst-case input of say ptn=xxxxy and txt=xxxxxxxxxxxxxxxxxxxxy, which will cause it to be O(nm) I believe. The logic in the algorithm resets the counter for ptn, and only increments the index of txt by 1.

You can compare your execution to the Boyer–Moore sub-string search algorithm and see how different it is to yours:

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

Upvotes: 2

Related Questions