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

How to check all previous values in an SQL Server table via c# or SQL code
I have a table to record staffs enter and exit times. I want to implement this logic: when they enter their code in a text box, the code should go through all previous values, if that name has a clockIn time value but no ClockOut time value, the system should record the time in the ClockOut column.
But if there is no clockIn and no ClockOut for that name, the system should record time and store it in ClockIn column (and if there is clockIn and clockout values presented before in the table for that name then system should start a new row with that name, and record the time in clockIn column).
Why do I say it should check all of the previous records? Because there are several employees who would enter their code in the program in the morning in any order and at night all of them will enter their code not in a predetermined order. So the system should figure it out who has clockedIn before to Clock it out and who has not done anything before to clock it in.
This maybe possible with a composition of C# and SQL code so I would be thankful for any help.
I would like to know the code to check the previous records in SQL (or maybe in C#).
My real Staffs Info table:
CREATE TABLE [dbo].[tbl_attendanceMembers] ( [Id] INT IDENTITY (1, 1) NOT NULL, [memberCode] NVARCHAR (20) NULL, [name] NVARCHAR (20) NULL, PRIMARY KEY CLUSTERED ([Id] ASC) );
Attendance sheet table:
CREATE TABLE [dbo].[tbl_attendanceSheet] ( [Id] INT IDENTITY (1, 1) NOT NULL, [memberCode] NVARCHAR (20) NULL, [name] NVARCHAR (20) NULL, [date] DATE NULL, [clockin] TIME NULL, [clockout] TIME NULL, [delay] TIME NULL, [HouresWorked] TIME NULL, [desc] NVARCHAR (150) NULL, PRIMARY KEY CLUSTERED ([Id] ASC) );
My own attempt(which does not include the conditional part I mentioned above): Input ClockIN:
CREATE procedure InputClockIn @InputCode nvarchar(20), @InputName nvarchar(20), @InputDate nvarchar(20), @InputTime nvarchar(20) as Insert Into tbl_attendanceSheet(memberCode,name,date,clockin) Values (@InputCode,@InputName,@InputDate,@InputTime)
Input ClockOut:
CREATE procedure InputClockOut @InputTime nvarchar(20) as Insert Into tbl_attendanceSheet(clockOut) Values (@InputTime)
what I want presented in another way: lets assume this is my table:
[memberCode]  [name]  [ClockIn] [ClockOut]
In the morning Alex comes and clocks in
[memberCode]  [name]  [ClockIn] [ClockOut] 121 Alex 09:00:00
Jaimy comes and clocks in
[memberCode]  [name]  [ClockIn] [ClockOut] 121 Alex 09:00:00 122 jamy 09:00:20
Neo comes and clocks in
[memberCode]  [name]  [ClockIn] [ClockOut] 121 alex 09:00:00 122 jamy 09:00:20 123 Neo 09:00:25
Neo Leaves:
[memberCode]  [name]  [ClockIn] [ClockOut] 121 alex 09:00:00 122 jamy 09:00:20 123 Neo 09:00:25 13:00:00
Neo Comes
[memberCode]  [name]  [ClockIn] [ClockOut] 121 Alex 09:00:00 122 Jamy 09:00:20 123 Neo 09:00:25 13:00:00 123 Neo 18:00:00
At night, Jamie leaves:
[memberCode]  [name]  [ClockIn] [ClockOut] 121 Alex 09:00:00 122 Jamy 09:00:20 22:00:00 123 Neo 09:00:25 13:00:00 123 Neo 18:00:00
Neo Leaves:
[memberCode]  [name]  [ClockIn] [ClockOut] 121 Alex 09:00:00 122 Jamy 09:00:20 22:00:00 123 Neo 09:00:25 13:00:00 123 Neo 18:00:00 23:00:00
Alex Leaves:
[memberCode]  [name]  [ClockIn] [ClockOut] 121 Alex 09:00:00 00:00:00 122 Jamy 09:00:20 22:00:00 123 Neo 09:00:25 13:00:00 123 Neo 18:00:00 23:00:00
ofcource I need a date column as well but I omited it due to simplicity. This is my idea for an attendance sheet. If you want to add something to make it better, I would appreciate it.

Measure the time with time.time() and Keydown
I got sounds that I play from a list called
sounds
. It plays a sound, store the time when the sound is played instart
, waits 6 seconds and plays the next sound from the list. Now I want to capture a reaction time between these 6 seconds with a keydown. If the condition is true then I click the button and it captures the time and store it inend
. Then, the difference betweenend
andstart
should give me the result. The problem is, that it does not measure the time right. It always gives me millisconds, even if I way longer bfore I click. I wonder what I am doing wrong here?start = time.time() for i in range(len(arr)): pygame.mixer.music.load(sounds[i]) pygame.mixer.music.play() for e in pygame.event.get(): if e.type == pygame.KEYDOWN: if e.key == pygame.K_RIGHT: if condition: end = time.time() diff = end  start while pygame.mixer.music.get_busy(): time.sleep(6)

Unusual time for allocating and copying a Numpy array
I have recently observed a problem in allocation and copying of Numpy arrays:
Array allocation takes constant time (wrt. array size); copying the contents of another array into the allocated array, takes also some amount of time which increases with array size. However, the problem is that the time elapsed for doing both operations, allocation and copying, is not merely the sum of the time for either of the operations (see the figure below):
t(allocation + copy) > t(allocation) + t(copy)
.I cannot see the reason for the extra time elapsed (which rapidly increases with size).
Here's the code I used for timing. The timing is performed under Debian Stretch with an Intel Core i3 CPU (2.13 GHz).
import numpy as np import gc from timeit import default_timer as timer import matplotlib.pyplot as plt def time_all(dim1): N_TIMES = 10 shape = (dim1, dim1) data_1 = np.empty(shape, np.int16) data_2 = np.random.randint(0, 2**14, shape, np.int16) # allocate array t1 = timer() for _ in range(N_TIMES): data_1 = np.empty(shape, np.int16) alloc_time = (timer()  t1) / N_TIMES # copy array t1 = timer() for _ in range(N_TIMES): data_1[:] = data_2 copy_time = (timer()  t1) / N_TIMES # allocate & copy array t1 = timer() for _ in range(N_TIMES): data_3 = np.empty(shape, np.int16) np.copyto(data_3, data_2) alloc_copy_time = (timer()  t1) / N_TIMES return alloc_time, copy_time, alloc_copy_time #END def # measure elapsed times gc.disable() # disable automatic garbage collection times_elapsed = np.array([(size, ) + time_all(size) for size in np.logspace(2, 14, 1<<8, endpoint=True, base=2, dtype=int)]) gc.enable() # plot results plt.plot(times_elapsed[:,0], times_elapsed[:,1], marker='+', lw=0.5, label="alloc") plt.plot(times_elapsed[:,0], times_elapsed[:,2], marker='+', lw=0.5, label="copy") plt.plot(times_elapsed[:,0], times_elapsed[:,3], marker='+', lw=0.5, label="alloc©") plt.xlabel("array dim.") plt.legend() plt.savefig("alloc_copy_time.svg")

Plot basin of attraction for unforced duffing equation with matplotlib
I am evolving the system using a symplectic integrator of sixth order, this system has a pair of attractors on each side of the phase space. My attempt to plot the basins of attraction is by defining a grid of points in the phase space and evolving each of the points using the integrator, when the system enters a specific zone of the phase space (the attractor)(and what I can't manage to write correctly in the code) the integrator will stop and give a value 0 or 1 to the initial point, this will result in a grid of points with values 0 or 1, and when I plot the function's contour this will hopefully show the basins of attraction:
#yoshida 6th order symplectic integrator for attractor import math as m import numpy as np import matplotlib.pylab as plt #Hamilton equations def A(m0, a0, b0, x0, v0, gamma0): #p point return a0*x0/m0  b0*x0*x0*x0/m0 gamma0*v0 def V(m0,p0): #x point return p0/m0 def f(x0, p0, m0, a0, b0): #contour function return p0**2/(2*m0)a0*x0**2/2+b0*x0**4/4 gamma=0.1 #dissipation parameter #constants for integrator dos=2.**(1./3.) m=1. a=0.25 b=0.01 a1=0.78451361047756 b1=0.39225680523878 a2= 0.23557321335936 b2=0.51004341191846 a3=1.1776799841789 b3=0.47105338540976 a4=1.3151863206839 b4=0.068753168252520 a5=1.1776799841789 b5=0.068753168252520 a6=0.23557321335936 b6=0.47105338540976 a7=0.78451361047756 b7=0.51004341191846 a8=0 b8=0.39225680523878 xc = np.linspace(9, 9, 100) #contour grid yc = np.linspace(4, 4, 100) #contour grid xp = np.linspace(9, 9, 100) #grid for points yp = np.linspace(4, 4, 100) #grid for points XC, YC = np.meshgrid(xc, yc) #grid ZC = f(XC, YC,m,a,b) def yoshi(xx,pp): #function of yoshida integrator x=[xx] #initial position p=[pp] #initial momentum dt=0.001 #paso del integrador t=[0.] #lista de tiempo H=[p[0]*p[0]/(2.*m)a*x[0]*x[0]/2.+b*x[0]*x[0]*x[0]*x[0]/4.+gamma*p[0]*x[0]] #list of the energy i=0 while True: e=2 print (i) vini=p[i]/m v11=V(m,p[i])+b1*A(m,a,b,x[i],vini,gamma)*dt x11=x[i]+a1*v11*dt v12=v11+b2*A(m,a,b,x11,v11,gamma)*dt x12=x11+a2*v12*dt v13=v12+b3*A(m,a,b,x12,v12,gamma)*dt x13=x12+a3*v13*dt v14=v13+b4*A(m,a,b,x13,v13,gamma)*dt x14=x13+a4*v14*dt v15=v14+b5*A(m,a,b,x14,v14,gamma)*dt x15=x14+a5*v15*dt v16=v15+b6*A(m,a,b,x15,v15,gamma)*dt x16=x15+a6*v16*dt v17=v16+b7*A(m,a,b,x16,v16,gamma)*dt x17=x16+a7*v17*dt v18=v17+b8*A(m,a,b,x17,v17,gamma)*dt x18=x17+a8*v18*dt x.append(x18) p.append(m*v18) xi=x[i] pi=p[i] t.append(t[i]+dt) H.append(pi*pi/(2.*m)a*xi*xi/2.+b*xi*xi*xi*xi/4.+gamma*pi*xi) if (pi<'0.86' and pi>'0.86' and xi<'3.5' and xi>'6.17'): #my attempt for giving values e=0 break if (pi<'0.86' and pi>'0.86' and xi>'3.5' and xi<'6.17'): e=1 break i=i+1 if (e=='0'): return 0 if (e=='1'): return 1 XP, YP = np.meshgrid(xp, yp) #grid for contour ZP = yoshi(XP, YP) #function applied to the whole grid #Attractors plot plt.contourf(XP, YP, ZP, 2) plt.colorbar(); plt.title('Atractores') plt.savefig('atractor.png', bbox_inches='tight') plt.clf()
This attempt of the code seems to be trapped in the while loop forever, and I think it does not read correctly the "if" condition I am trying to impose. Is there a way I can solve this?

Show <marquee> tag in a single row
I have the following code but it shows marquee output in 2 rows, I want it to appear in a single row.
Check screenshot.. Please help.
I know marquee is deprecated but I have to use it. Any help would be highly appreciated.
Thank You
<?php $sql = $dbh>prepare ("SELECT fromcity, tocity from tblbooking order by id DESC LIMIT 2"); $sql>execute() ; ?> <h3 style="color: #f52d31; textalign: center; backgroundcolor: #8080807a;"> Latest Rides </h3> <marquee> <?php while( $row = $sql>fetch()) : ?> <div> <tr> <li style="fontsize: 20px; color: red; liststyle: none; backgroundcolor: #cac2c2b8; width: 20%;"> <i class="fa falocationarrow" ariahidden="true"></i> Origin : <td><?php echo $row['fromcity']; ?></td> </li> <li style="fontsize: 20px;color: red; liststyle: none; backgroundcolor: #cac2c247; width: 20%;"> <i class="fa famapmarker" ariahidden="true"></i> Destin : <td><?php echo $row['tocity']; ?></td> </li> </tr> </div> <br> <?php endwhile ?> </marquee>

Print statement not printing after while loop
Why is the print statement not working when I run this code? If I put a print statement in the while loop, it prints. However, after the while loop it doesn't work. enter image description here

Complexity class definition issue
What is the exact definition (formal and informal) of coP?
Like P here

Find number of pairs of disjoint sets in a list of sets
The problem statement is as follows: given a list of n sets, each containing k integers, find the number of pairs of disjoint sets. Suppose the possible elements of the sets are positive and bounded above by c > n, and suppose k << n.
I'm trying to come up with an efficient algorithm to solve this faster than O(kn^2), which is the runtime of the naive solution.
The best strategy I could come up with involves iterating through each set in the list, and hashing the elements of the set, such that each element in the set maps to a set of the indices of the sets that contain it. Then, for the current set in the iteration, use its c elements as keys, and consider the union of the c sets of indices that are given as values by the hashtable. This resulting set of indices represents the number of sets encountered thusfar that are nondisjoint with the current set, which we can use to find the number of disjoint sets. Summing this value over the entire iteration yields a correct answer. However, since the union operation is O(n), this strategy does no better than the naive solution.
What is the most efficient possible solution for this problem?

catalan numbers recursive tree
I was trying to calculate time complexity using recursive tree but i am unable to reach at result ,I Know we have to calculate no of recursive calls in each stage ,But it is hard to understand recursion inside loops Please someone help me
NOTE>I know this is not the best way to calculate catalan numbers more appropriate solution will be is using DP
#include<iostream> using namespace std; // A recursive function to find nth catalan number unsigned long int catalan(unsigned int n) { // Base case if (n <= 1) return 1; // catalan(n) is sum of catalan(i)*catalan(ni1) unsigned long int res = 0; for (int i=0; i<n; i++) res += catalan(i)*catalan(ni1); return res; } // Driver program to test above function int main() { for (int i=0; i<10; i++) cout << catalan(i) << " "; return 0; }