naive algorithm implementation

Question

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 ");
    }
}

It is giving expected results you said. Then what is the wrong? — Mukit09
– Mukit09, Commented Feb 7, 2019 at 2:59
It hasn't O(n) complexity looks like O(n²) - without realy calculating. the while is hiding a nested loop. (And skimming over it I am not sure if this is realy naive ) — kai
– kai, Commented Feb 7, 2019 at 3:06
Thank you very much! Could i know the reason that u're not sure whether this is Naive? any difference in my logic? — RusJaI
– RusJaI, Commented Feb 7, 2019 at 13:43

Timothy T. · Accepted Answer · 2019-02-07 03:26:12Z

2

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

edited Feb 7, 2019 at 3:26

answered Feb 7, 2019 at 3:17

Timothy T.

1,1111 gold badge14 silver badges26 bronze badges

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

3 Comments

RusJaI Over a year ago

Thank you very much!! plz could i know why did you say that it wont be efficient? Since it's Naive so that it has O(n^2) complexity or this code is difference from Naive algo in someway?

Timothy T. Over a year ago

Think about the definition of a 'naive algorithm', what does it mean? I would say that it is like the first method a child would think of to solve a problem -- it will get the job done, but it will probably not be the 'best' solution. It will eventually solve the given problem, but what was the time and memory spent to do so? The naive algorithm is one where it is not efficient in terms of time (and perhaps also memory). That's where the big O notation comes in -- it's a standardized way of denoting time and space complexity.

Timothy T. Over a year ago

By the way, if this answer helped do accept this as the solution (tick symbol beside my answer) so that we can close this. If there are anything else you would like to clarify we can take this into chat -- don't want to have too long comment bodies.

Collectives™ on Stack Overflow

naive algorithm implementation

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related