I been studyng DSA and Big O Analysis during last year ,but I been strugglin trying to calculate this times complexity . This is from an exercise but to make it simple I just isolated what is causing me confusion .

Hope someone could give me some orientation.

This is the small code to analysis ,as i show examples i will be changing the word and the prefix data .

String prefix = "TAXI";
String word= "TAXI";

while (word.indexOf(prefix)!=0){
   prefix= prefix.substring(0,prefix.length()-1);
}

Just for clarification :

IndexOf is (N * M ) in Java
susbtring is (N) in Java
From now M is the length of the Prefix and N is the length of the Word

Scenario 1

Prefix is the same as Word :

String prefix = "TAXI";
String word= "TAXI";

while (word.indexOf(prefix)!=0){
   prefix= prefix.substring(0,prefix.length()-1);
}

Number of times While loop is executed = 0;

Though IndexOF has (N * M ) complexity ,we know we are gonna have M comparisons.

N[0] == M[0] N[1] == M[1] N[2] == M[2] N[3] == M[3]

We can say this is the best case = O(M)

Scenario 2

Prefix and Word only share the first Letter

  String prefix = "TAXI";  - > Length = 4
  String word= "TXXXXXXX"; - > Length = 8

   while (word.indexOf(prefix)!=0){
       prefix= prefix.substring(0,prefix.length()-1);
   }

Number of times IndexOf executed = 4 , so M times
Number of times While loop is executed = 3 , so M times - 1

Lets think the real number of comparisions IndexOf executes each time :

Taxi - > Index Of , Number of comparisions 9
Tax- > Index Of , Number of comparisions 8
Ta- > Index Of , Number of comparisions 7
T- > Index Of , Number of comparisions 1

Total Comparision = 26

We could say the total is = (N * M - M 1) ,removing the constant = > (N * M - M ) = > (N * M)

What about the Substring method ?Is gonna execute 3 times ,and each time is gonna execute this number of comparisions :

(M) Comparisions
(M - 1 ) Comparisions
(M - 2 ) Comparisions

So ,(M) (M-1) ( M -2) = M*(M 1)/2. = O (M * M)

Now that we have the full picture , the worst case ( for the moment) is : BIG O (N * M M² )

Scenario 3

The prefix exist , but never in the 0 position :

String prefix = "TAXI"; = > Length = 4
String word= "XXTAXI";  = > Length = 6

   while (word.indexOf(prefix)!=0){
       prefix= prefix.substring(0,prefix.length()-1);
   }

Number of times IndexOf executed = 4 , so M times
Number of times While loop is executed = 3 , so M times - 1

Lets think the real number of comparisions IndexOf executes each time :

Taxi - > Index Of , Number of comparisions 6
Tax- > Index Of , Number of comparisions 5
Ta- > Index Of , Number of comparisions 4
T- > Index Of , Number of comparisions 3

Now here i have a problem ,where i found two different ways of expressing this in a Big O way :

Total comparisions = (N) (N-1) ( N-2) (N -3) = N*(MN1)/2. = O (N * N)

Or i can think the number of comparisions like the following sum :

(N - M- M) ( N - M - M 1 ) (N -M - M 2 ) ( N - M - M 2) = (6 - 0 ) ( 6 - 1 ) (6 - 2) (6 - 3)

= > (N * M - (something) ) = > Removing constants > (N * M )

So ,which is the correct Big o for this case ? (N * M M² ) or (N * N M² )

Scenario 4 - Last one

Worst index Of scenario.

String prefix = "TTTK";  = > Length = 4
String word= "TTTTTK";   = > Length = 6

   while (word.indexOf(prefix)!=0){
       prefix= prefix.substring(0,prefix.length()-1);
   }

When searchin a String inside another one ,this is the worst case scenario,where you should practically all combinations.

Number of times IndexOf executed = 2
Number of times While loop is executed = 1

In this example ,it will have to do N * M real combinations the first time ,that that is almost all, because as the Substring removed the last character of Prefix , now ,the second time it will execute the index of ,it will only need to perform M operations,it will find the subtring in the most fast way .

Lets think the real number of comparisions IndexOf executes each time :

TTTK- > Index Of , N * M
TTT- > Index Of , M

The substring will only run 1 time M times = > O(M) .

The final Big O i have for this case is = (NM M ) M > Removing the constants = N M

My 2 Big questions here are :

Are 4 analysis are correct ?
Does the second Scenario is the worst case complexity?

Thank you in advance!

CodePudding user response：

Your reasoning is flawed. You are trying to come up with scenarios that are too specific and where the strings are too small. Time complexity is useful for determining how the time taken by an algorithm grows as the input size grows.

To answer your questions:

your analyses are correct insofar as the resulting numbers of comparisons are correct (for scenario 3, your equations don't make sense to me, but the complexity would be O(N*M M^2), for more or less the same reason as in scenario 2);
no, your scenario 2 is not the worst possible case.

The worst possible case is when the loop runs O(M) times, each time performing an indexOf in O(N*M) and a substring in O(M), making the overall time complexity O(M*N*M M*M) = O(N*M^2).

Here is an example of that worst case. Consider a prefix made of M/2 times the letter A followed by M/2 times the letter B, and a word made of N times the letter A.

String prefix = "AAA...BBB"; // length M
String word = "AAAAA..."; // length N

Because only half the prefix is contained in the word, the loop will run M/2 times (removing all occurences of B). The condition will be evaluated M/2 1 times, but that 1 does not matter in the overall complexity.

Each time, the indexOf operation is performed, doing M/2 comparisons (all the letters A in the prefix) for every letter in the word (except the last M/2-1, but that doesn't matter if N > M/2), for a time complexity of O(N*M/2) = O(N*M).

Each time, the substring operation is performed on the prefix, and its size varies between M and M/2, for a time complexity of O(M).

Thus the total time complexity in this example is M/2 * (O(N*M) O(M)) = O(N*M^2).