Capital N vs small n in time complexity

See also questions close to this topic

• Palindromes in a tree

  I am looking at this challenge:

  Given a tree with N nodes and N-1 edges. Each edge on the tree is labelled by a string of lowercase letters from the Latin alphabet. Given Q queries, consisting of two nodes u and v, check if it is possible to make a palindrome string which uses all the characters that belong to the string labelled on the edges in the path from node u to node v.

  Characters can be used in any order.

  N is of the order of 10⁵ and Q is of the order of 10⁶

  Input:

  N=3
  u=1 v=3 weight=bc
  u=1 v=2 weight=aba
  Q=4
  u=1 v=2
  u=2 v=3
  u=3 v=1
  u=3 v=3

  Output:

  YES
  YES
  NO
  NO

  What I thought was to compute the LCA between 2 nodes by precomputation in O(1) using sparse table and Range minimum query on Euler tower and then see the path from LCA to node u and LCA to node v and store all the characters frequency. If the sum of frequency of all the characters is odd, we check if the frequency of each character except one is odd. If the sum of frequency of all the characters is even, we check if the frequency of each character is even. But this process will surely time out because Q can be upto 10⁶.

  Is there anyone with a better algorithm?
• Time complexity for a for loop with a multi-variable condition statement

  A. What is the complexity (big-O) of the following code fragment?

  for (i = 0; (i < n) || (i < m); i++) {
  sequence of statements
  }
  

  The best i could come up with is the following.. if n is less then m O(n) else O(m) I have no clue how to write big-o in the case where there are two variables.

  I know this is a very corner case and basic time complexity question so i do not mind removing it after I get some clarification.
• I'm merge sorting int arrays of length 10,000 to 75,000. I am getting strange sort times. Why might this be?

  I am doing an assignment for my algorithms class and I have to demonstrate that internal merge sort has a time complexity of O(nlogn). To do this I made arrays ranging in length from 10,000 elements long to 75,000 elements long. Then I load the array with random numbers < 10,000, and output the array length to the console with how long it took to sort.

  The strange result is that some take ~15 milliseconds give or take and then others take 0 milliseconds, even if the array is tens of thousands of integers longer. Any idea of why this may be? I can upload a screen shot of my output, but someone needs to approve it because I don't have enough "reputation". I have checked the arrays. They do appear to be sorted after calling the mergeSort() method.

   public static void main(String[] args){
      int[] dataLength = {10_000, 15_000, 20_000, 25_000, 30_000, 35_000, 40_000, 45_000, 50_000, 
                          55_000, 60_000, 65_000, 70_000, 75_000};
    //        internal merge sort
      for (int i = 0; i < dataLength.length; i++) {
          int[] input = new int[dataLength[i]];
  
          for (int j = 0; j < input.length; j++) {
              input[j] = random.nextInt(10000);
          }
  
          long startTime = System.currentTimeMillis();
          mergeSort(input, 0, input.length);
          long endTime = System.currentTimeMillis();
  
          System.out.println("Length of array is: " + input.length  + ". The sorted array: "
                  + Arrays.toString(input));
          System.out.println("Internal sort with " + dataLength[i] + " items took: " +
                  (endTime - startTime) + " milliseconds");
      }
   }
  
   public static void mergeSort(int[] input, int start, int end) {
      if (end - start < 2) {
          return;
      }
  
      int mid = (start + end) / 2;
      mergeSort(input, start, mid);
      mergeSort(input, mid, end);
      merge(input, start, mid, end);
      return;
  }
  
  public static void merge(int[] input, int start, int mid, int end) {
      if (input[mid - 1] <= input[mid]) {
          return;
      }
   //        index of "left" array
      int i = start;
   //        index of "right" array
      int j = mid;
      int tempIndex = 0;
      int[] temp = new int[end - start];
  
      while (i < mid && j < end) {
          temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
      }
   //        optimizes the merge. If there are elements in the left array we just copy them back
   //        into the input array instead of merging them with the temp array first
      System.arraycopy(input, i, input, start + tempIndex, mid - i);
      System.arraycopy(temp, 0, input, start, tempIndex);
      return;
  }
  
• Discrete optimization approach for holiday travel problem

  I’m new to discrete optimization techniques and I’m trying to determine the best or appropriate way to model/attack a specific problem.

  I call it the Holiday Travel for Picky Families problem...

  Here’s the concept:

  1. There are a network of airports with various flight paths between each airport.
  2. There are a fixed number of flights between any two given airports (0..N)
  3. There’s a list of families requiring traveling for the holidays at exactly the same start and end date, removing the time-dimension from the problem. Each family having a specific pair of endpoint airports.
  4. Each family is composed of 1..6 members.
  5. Members of a family must travel together on a flight in a contiguous section of seats.
  6. If a route for a given family requires more than one leg/hop, the family must be able to sit in the exact same seats on both flights.
  7. Not all possible flight routes for a given family will be allowed, but there’s a guaranteed 3 potential routes at minimum, with 2 routes being fully diverse.
  8. Extending #6, every set of family seat assignments on the chosen route must also be reserved for that family on a fully redundant route in the allowed list. Effectively two diverse routes must be saved for each family, with matching seat assignments on both routes.
  9. Each flight has a maximum seat capacity.
  10. For the purposes of this problem, the seatmap on a flight should be represented as a linear 1D layout of seats.

  I’m guessing this would fall under a class of routing or scheduling problems in Discrete Optimization or Satisfiability. But I’m having trouble figuring out how to get started. Any references or approaches I should look at? I'd like to figure out how to model and represent the constraints to an existing generic solver ideally.

  Thanks!
• Python: Binary Search - "Find the first occurrence"

  having a bit of trouble with this one. I have included what I have below. When I submit it, it keeps saying "Program timed out" for some reason. I am not sure what to do next. It works to a certain degree, ie, some tests work, not the last test just doesn't work. What do you suggest?

  I have included a screenshot of the question, as well as what I have so far.

  Here is the note (pseudocode) from class, I just need to modify this to modify it to print the first occurance of the target in the ordered_list. If the target does not exist in the list, it must return None.

  Thank you in advance!!

  The Question: You are to write the code of a Python function

  binsearch first(ordered list, target)

  that, given a nonempty ordered list of items and a target item, all of the same type, returns the index of the first occurrence of the target in the list, if the target is in the list, and None otherwise.

  For example, the call binsearch first([1, 3, 3, 7, 9], 3) should return 1 since the first 3 is at index 1. Similarly, the call binsearch first([1, 3, 3, 7, 9], 9) should return 4, and the call binsearch first([1, 3, 3, 7, 9], 5) should return None.

  You may not assume anything about the type of the items, other than that they are orderable. For example, items could be strings and the call binsearch first(["Alice", "Bob", "Chloe", "Chloe", "Dave"], "Chloe") should return 2.

  Your program will be evaluated for efficiency and style. For full credit, it may only make a single test for equality (it may only have a single “==” comparison which, additionally, may not be within any loop). That is, the only equality test happens at the end of execution, just before returning.

  Restrictions: Recursion is not allowed for this problem. allowed to use any operations other than

  Furthermore, you are not

  • , − , // , × , < ,

  and (once) ==

  Of course, all builtins and library functions related to search are also disallowed: you have to do the coding yourself.

  def binsearch_first(ordered_list, target):
      left = 0
      right = len(ordered_list) - 1
      count = 0
      while left <= right:
          mid = (left + right) // 2
          count = count + 1
          if ordered_list[mid] == target:
              while mid > 0 and ordered_list[mid - 1] == target:
                  mid = mid - 1
              return mid
          elif target < ordered_list[mid]:
              right = mid - 1
          else:
              left = mid + 1
      return None

  Find the first occurrence
• Minimax AI for connect 3 only working for 2 turns

  I have been working on this AI and it will put the two pieces in the leftmost column and then stop. When it stops I can play it like a human by manually clicking for it. What am I doing wrong?

  public int minimax(Player[][] state, int depth, Player player){
      int maxEval = (int) Double.NEGATIVE_INFINITY;
      int minEval = (int) Double.POSITIVE_INFINITY;
      int eval;
      if(depth == 3 || player == NONE){
          return 0;
      }
  
      for(int c = 0; c<GRID_COLUMNS; c++){
          int r = free(state, c);
          if(free(state, c)>=0){
              continue;
          }
          if( player == PLAYER_X){
              state[r][c] = PLAYER_X;
              eval = minimax(state, depth-1, opponentOf(PLAYER_X));
              maxEval = Math.max(maxEval, eval);
              state[r][c] = NONE;
          }
          else if(player == opponentOf(PLAYER_X)){
              state[r][c] = opponentOf(PLAYER_X);
              eval = minimax(state, depth+1, PLAYER_X);
              minEval = Math.min(minEval, eval);
          }
          state[r][c]=NONE;
      }
  
      switch (player){
          case PLAYER_X:
              return maxEval;
          case PLAYER_O:
              return minEval;
          default:
              return 0;
      }
  }
  
  public int getBestColumn(Player[][] state, Player player){
      return minimax(state, 3, opponentOf(player));
  }