title: Big-O analysis of a sub-string of string algorithm. Does O(n*logn) simplify?
body: <p>Hello and thanks for reading. I am working on a homework assignment. I have created a method that compares to strings to see if one is a sub-string of another. I am aware there is already a built in method to do this. The assignment does not allow me to use them. Anyway, the below code is working.</p>
  
  <p>I have to analyze the complexity of the algorithm using Big-O notation. From what I can see the outer loop runs in linear time because it simply runs as many times as the length of the string. Thus: O(n)</p>
  
  <p>The inner loop is different, it may or may not happen, and if it does it may finish before the the length of the second string which is it's input. Thus: O(logn)</p>
  
  <p>So it appears to me the the complexity is O (n*logn). Does this simplify to O(n) or does it stay in its current form? Or am I wrong about the inner loop being O(logn)?</p>
  
  <pre><code>import java.util.Scanner;
  
  public class HW3q6 {
  public static void main(String[] args) {
      Scanner userInput = new Scanner( System.in );
      System.out.println("Please enter the first string: ");
      char[] charArray1 = userInput.nextLine().toUpperCase().toCharArray();
      System.out.println("Please enter the second string: ");
      char[] charArray2 = userInput.nextLine().toUpperCase().toCharArray();
  
      System.out.println("The second string is a substring of the first: " + subString(charArray1, charArray2));
  
  }
  
  private static boolean subString(char[] charArray1, char[] charArray2) {
      int counter = 0;
      for (int i = 0; i &lt; (charArray1.length + 1) - charArray2.length ; i++) {
          if (charArray1[i] == charArray2[0]) {
              for (int n = 0; n &lt; charArray2.length; n++) {
                  if (charArray1[i+n] == charArray2[n]) {
                      counter++;
                  }
              }
              if (counter == charArray2.length) {
                  return true;
              } else
                  counter = 0;
          }
      }
      return false;
  
  }
  }
  </code></pre>