Capital N vs small n in time complexity
I came accross the following question and it made me confused:
A quadratic algorithm with processing time T(n) = cn2 spends T(N) seconds for processing N data items. How much time will be spent for processing n = 5000 data items, assuming that N = 100 and T(N) = 1ms?
What is the difference between N and n in time complexity?
1 answer

There is no special meaning for capital
N
vs lowercase lettern
in time complexity. In this contextn
andN
are just used as different values for the same variable, it would make no difference if instead ofN
they gave youx
.Important, when I use A => B, the => arrow means "A equals to B", or if you prefer "A ends up being B"
Now, having in mind the original quadratic function
T(n) = c*n^2
 If
N = 100
andT(N) = 1ms
then they are telling you thatT(100) = 1ms
=>1ms = c * 100^2
.  What you deduce from the previous statement is
1ms = c * 100^2
=>c = 1ms / 100^2
. Now just replace
c
andn
in the original formula that isT(n) = cn2
(beingn = 5000
):T(5000) = (1/100^2) * 5000^2
=>T(n) = 2.500ms
=>T(n) = 2,5s
 If
See also questions close to this topic

Palindromes in a tree
I am looking at this challenge:
Given a tree with N nodes and N1 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^{5} and Q is of the order of 10^{6}
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=3Output:
YES
YES
NO
NOWhat 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^{6}.
Is there anyone with a better algorithm?

Time complexity for a for loop with a multivariable condition statement
A. What is the complexity (bigO) 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 bigo 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:
 There are a network of airports with various flight paths between each airport.
 There are a fixed number of flights between any two given airports (0..N)
 There’s a list of families requiring traveling for the holidays at exactly the same start and end date, removing the timedimension from the problem. Each family having a specific pair of endpoint airports.
 Each family is composed of 1..6 members.
 Members of a family must travel together on a flight in a contiguous section of seats.
 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.
 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.
 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.
 Each flight has a maximum seat capacity.
 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 ﬁrst 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 ﬁrst 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 eﬃciency 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

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, depth1, 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)); }