Counting algorithms while loop's time complexity
I have found that questions were already created regarding these type of topics, but they looked very simple examples. I know how to count time complexity of for loops, but how would I go about counting this while loop inside the method?
public static void QuickSort(DataArray items, int left, int right)
{
int i = left, j = right;
double vid = items[(left + right) / 2];
while (i <= j)
{
while (items[i] < vid)
i++;
while (items[j] > vid)
j;
if (i <= j)
{
items.Swap(j, i, items[j], items[i]);
i++;
j;
}
}
if (left < j)
QuickSort(items, left, j);
if (i < right)
QuickSort(items, i, right);
}
See also questions close to this topic

Measuring processing time in R and then accessing it through a variable
I am a beginner and I would like to measure time of a spatial process and input it in a variable. Is there a way to do that with R. I have tried using
library(tictoc)
but I think the measurements are inaccurate when inputting them in a variable, because my time is 2 secs and using thetoc()
function I get the value 8320. 
How to format hour with offset
I have an integer representing a UTC hour and I have a UTC offset of a timezone. How can I get the equivalent hour for that timezone? So for example:
date = "Fri Dec 01 12:06:35 +0000 2017" utc = "18000" ts = datetime.strptime(date, '%a %b %d %H:%M:%S +0000 %Y')

Forked processes printing same time
In the following code I don't understand why the forked processes (the ten of them) print the same time. As far as I understand it, each process should wait a random amount of time (up to 15 seconds) and then print the time as of their end. Can someone explain why they print the same time?
int main() { int x, i; for (i = 0; i < 9; i++) { x = fork(); if (x == 0) { sleep(rand() % 15); printf("%d ended: %ld\n", i, time(NULL)); exit(0); } } while (wait(NULL) != 1); exit(0); }

Running while loops in the background, and threading, python 2.7
dumb question I know, but I am having some major issues with this.
I have built a command line menu system that allows you to select options and execute different parts of the program.
Here is the issue I am running into.
When option 7 is pressed, it calls a function, that calls a def in a class that starts the program main loop and outputs data to an SQL database.
What I want it to do is execute the deff in the class, and then return to the main menu, allowing users to select a different option.
I have tried with threading and I have it working, however, it does not return the console to the menu, as the def in the class is a while loop.
How do I get it to execute the while loop in the background while returning to the main menu?
Thanks!

When click within the random squares it says "You clicked!" only when it draws the next square and not when you initially click
import turtle import random import time t1 = turtle.Turtle() t2 = turtle.Turtle() s = turtle.Screen() def turtle_set_up(): t1.hideturtle() t2.hideturtle() t2.penup() s.tracer(1, 0) def draw(): for i in range(2): t1.fd(400) t1.lt(90) t1.fd(400) t1.lt(90) def drawbox(): t2.pendown() for i in range(2): t2.fd(50) t2.lt(90) t2.fd(50) t2.lt(90) t2.penup() def box1(): X = random.randint(0, 350) Y = random.randint(0, 350) Xleft = X Xright = X + 50 Ytop = Y + 50 Ybottom = Y t2.goto(X, Y) drawbox()
Here is where it checks if your mouse click is within the box drawn. If it is, it erases the old box for a new one to be drawn every 3 seconds.
I don't understand why it waits to say "You clicked!" until the 3 seconds are up for the loop instead of saying it when you initially click.
I cant place a break command after the print statement that prints "You clicked!" because it's outside the loop.
between here
t_end = time.time() + 60 * 0.05 while time.time() < t_end: def get_mouse_click_coor(x, y): X_click = x Y_click = y if Xright > X_click > Xleft and Ytop > Y_click > Ybottom: print('You clicked!') s.onclick(get_mouse_click_coor) t2.clear()
and here
def starter(): turtle_set_up() draw() while 1: box1() starter()

Count the number of times a value in a data occurs
I'd like to count the number of times a value occurs in some data I have, and then print out the total. This is what I have so far:
def countOnes(sound): length = getLength(sound) sum = 0 for index in range(0,length): s = getSampleValueAt(sound,index) if s == 1: sum = sum + 1 print sum

computational complexity of Annoy
I am using Annoy for finding knearest neighbors of a doc2vec model. I want to compute the Computational complexity.
I am looking for the computational complexity of Annoy library.
I calculate the complexity of Annoy algorithm based on the steps mentioned in this page.
I assume:
 dimension is d
 size of data is n
 number of binary tree is T
Then the time complexity would be:
Preprocessing time: Build up a bunch of binary trees. For each tree, split all points recursively by random hyperplane
O(Tlogn)
Query time: Insert the root of each tree into the priority queue
O(T logn)
Until we have _search_k _candidates, search all the trees using the priority queue
O(Tn logk)
Remove duplicate candidates
O(Tk)
Compute distances to candidates
O(TKd)
Sort candidates by distance
O(TKlog(TK))
Return the top ones
The time complexity of Annoy library is :
O(Tlogn)+ O(T logn)+O(T n log k)+O(Tk)+O(TKd)+O(TKlog(TK))
Can anyone help me?

Time complexity of power() in three case
algorith1
A1 :y=1 pour i=1 à n faire y=y*x FPour
Algorithm2 A2 : puiss(x,n) Si (n=1) renvoyer x Sinon renvoyer y*puiss(x,n1) FSi pour
algorithm3 A3 : puiss(x,n) Si (n=1) renvoyer x Sinon tmp=puiss(x,n/2) renvoyer tmp*tmp

Running complexity of munkres library in Python
I have been trying to implement a 0(n^3) version of Hungarian algorithm. I came across the munkres library as they claim to have the running time of 0(n^3). By looking at their code I am not sure how do they measure 0(n^3) because it seems like 0(n^4).
def __step4(self): """ Find a noncovered zero and prime it. If there is no starred zero in the row containing this primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6. """ step = 0 done = False row = 0 col = 0 star_col = 1 while not done: (row, col) = self.__find_a_zero(row, col) if row < 0: done = True step = 6 else: self.marked[row][col] = 2 star_col = self.__find_star_in_row(row) if star_col >= 0: col = star_col self.row_covered[row] = True self.col_covered[col] = False else: done = True self.Z0_r = row self.Z0_c = col step = 5 print("In Step 4") return step def __find_a_zero(self, i0=0, j0=0): """Find the first uncovered element with value 0""" row = 1 col = 1 i = i0 n = self.n done = False while not done: j = j0 while True: if (self.C[i][j] == 0) and \ (not self.row_covered[i]) and \ (not self.col_covered[j]): row = i col = j done = True j = (j + 1) % n if j == j0: break i = (i + 1) % n if i == i0: done = True return (row, col) def compute(self, cost_matrix): """ Compute the indexes for the lowestcost pairings between rows and columns in the database. Returns a list of (row, column) tuples that can be used to traverse the matrix. :Parameters: cost_matrix : list of lists The cost matrix. If this cost matrix is not square, it will be padded with zeros, via a call to ``pad_matrix()``. (This method does *not* modify the caller's matrix. It operates on a copy of the matrix.) **WARNING**: This code handles square and rectangular matrices. It does *not* handle irregular matrices. :rtype: list :return: A list of ``(row, column)`` tuples that describe the lowest cost path through the matrix """ self.C = self.pad_matrix(cost_matrix) self.n = len(self.C) self.original_length = len(cost_matrix) self.original_width = len(cost_matrix[0]) self.row_covered = [False for i in range(self.n)] self.col_covered = [False for i in range(self.n)] self.Z0_r = 0 self.Z0_c = 0 self.path = self.__make_matrix(self.n * 2, 0) self.marked = self.__make_matrix(self.n, 0) done = False step = 1 steps = { 1 : self.__step1, 2 : self.__step2, 3 : self.__step3, 4 : self.__step4, 5 : self.__step5, 6 : self.__step6 } while not done: try: func = steps[step] step = func() except KeyError: done = True # Look for the starred columns results = [] for i in range(self.original_length): for j in range(self.original_width): if self.marked[i][j] == 1: results += [(i, j)] return results
These are the functions I was looking at and I think that for finding a zero function the complexity is 0(n^2) and since it is called in a while loop in step4 so it makes the complexity 0(n^3). Step 4 is called in a while loop in compute making the complexity 0(n^4). I want to know how they are claiming to have 0(n^3)?