Search results
Jump to navigation
Jump to search
Page title matches
- ...after the [[key signature]] in a piece of [[music]]. The two numbers in a time signature tell you how many of one kind of [[note (music)|note]] there are == Finding out what certain time signatures mean == ...3 KB (480 words) - 10:12, 20 June 2016
- ...n [[Albert Einstein]]'s theories of [[relativity]], there are two types of time dilation: <ref>Einstein, Albert and Infeld, Leopold 1938. ''The evolution o Experiments support both aspects of time dilation.<ref>{{cite book|last=Blaszczak Z. 2007|title=Laser 2006|url=https ...4 KB (681 words) - 09:08, 18 February 2017
- ...quickly but requires more memory than you have, you can try to spend more time solving the problem in the limited memory. ...writing down anything, which uses very little space, but might take a long time. ...3 KB (482 words) - 01:39, 25 October 2013
- = Mixing Time = The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...3 KB (562 words) - 13:56, 10 August 2011
- For any <math>u,v\in V</math>, the '''hitting time''' <math>\tau_{u,v}</math> is the expected number of steps before vertex <m This fact can be used to estimate the hitting time between two adjacent vertices. ...3 KB (510 words) - 15:06, 19 July 2011
- = Mixing Time= The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...27 KB (4,881 words) - 13:52, 31 July 2013
- = Mixing Time= The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...27 KB (4,881 words) - 07:04, 2 June 2014
- = Mixing Time= The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...23 KB (4,166 words) - 05:41, 22 December 2015
Page text matches
- ...after the [[key signature]] in a piece of [[music]]. The two numbers in a time signature tell you how many of one kind of [[note (music)|note]] there are == Finding out what certain time signatures mean == ...3 KB (480 words) - 10:12, 20 June 2016
- ...e <math>2\pi</math> encompassing one orbit is simply equal to ratio of the time of flight to the [[orbit]]al [[orbital period|period]] of one whole orbit ( ...846 bytes (137 words) - 09:46, 20 October 2014
- ...quickly but requires more memory than you have, you can try to spend more time solving the problem in the limited memory. ...writing down anything, which uses very little space, but might take a long time. ...3 KB (482 words) - 01:39, 25 October 2013
- ...fined as the [[integral]] of a [[Force (physics)|force]] with respect to [[time]]: : ''dt'' shows it is with respect to time. ...1 KB (158 words) - 00:15, 11 February 2016
- ...he distance the object travelled [[Division (mathematics)|divided]] by the time. where <math>d</math> is the distance and <math>t</math> is the time that has gone by. ...1 KB (195 words) - 08:01, 30 March 2017
- For any <math>u,v\in V</math>, the '''hitting time''' <math>\tau_{u,v}</math> is the expected number of steps before vertex <m This fact can be used to estimate the hitting time between two adjacent vertices. ...3 KB (510 words) - 15:06, 19 July 2011
- ...r example swinging from left to right and back to left. We will call this time T. If the pendulum length is ''L'', and the acceleration of gravity is g, t The regular motion of the pendulum can be used for time keeping, and pendulums are used to regulate pendulum [[clock]]s. ...1 KB (200 words) - 23:05, 20 March 2017
- = Mixing Time = The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...3 KB (562 words) - 13:56, 10 August 2011
- '''Big O Notation''' is a way of saying how much time it takes for a mathematical [[algorithm]] to run or how much [[computer mem ...hardware specifications and may produce the answer in different amounts of time should any program be run on them. The Big O notation, on the other hand, r ...4 KB (700 words) - 14:03, 20 September 2015
- ...n [[Albert Einstein]]'s theories of [[relativity]], there are two types of time dilation: <ref>Einstein, Albert and Infeld, Leopold 1938. ''The evolution o Experiments support both aspects of time dilation.<ref>{{cite book|last=Blaszczak Z. 2007|title=Laser 2006|url=https ...4 KB (681 words) - 09:08, 18 February 2017
- The '''wavelet transform''' is a [[time]]-[[frequency]] representation of a [[signal processing|signal]]. For examp * <math>b</math> denotes time shift of wavelet and ...2 KB (317 words) - 16:57, 23 January 2015
- ...four dimensions: three dimensions of space (x, y, z) and one dimension of time. Minkowski spacetime has a metric signature of (-+++) and is always flat. T ...s of the speed of light times the time coordinate is so that the units for time are the same as the units for space. Spacetime has the differential for arc ...3 KB (486 words) - 17:18, 1 September 2016
- The '''Lorentz factor''' is the factor by which time, length, and [[mass]] changes in for an object moving at speeds close to th == Time dilation == ...3 KB (527 words) - 04:29, 31 March 2017
- ...riable <math>X</math> (think that <math>X</math> is a cost such as running time of a randomized algorithm). We call this a '''tail bound''', or a '''tail i ...ed algorithm for a decision problem <math>f</math>, whose expected running time is within <math>T(n)</math> on any input of size <math>n</math>. We transfo ...3 KB (541 words) - 15:18, 21 July 2011
- ...nic motion''. When measuring motion, it is normal to make a [[graph]] with time on one axis and distance on the other. Sometimes, when something moves its ...ude]] is the biggest distance from the fixed point. The [[period]] is the time the weight takes to get back to the same point again (with the same speed a ...2 KB (431 words) - 21:21, 22 August 2017
- ...uote><math display="block">\text{velocity} = \frac\text{displacement}\text{time}</math></blockquote>For example, if an object moves 20 meters (m) to the le ...1 KB (172 words) - 21:31, 13 February 2017
- ...d the time for planet 1 to cover segment ''A''<sub>1</sub> is equal to the time to cover segment ''A''<sub>2</sub>. <br><br> (3) The total orbit times for ...ning a planet and the Sun sweeps out equal areas during equal intervals of time. ...3 KB (498 words) - 22:12, 30 May 2017
- ...ath>. And the following theorem is implied by the upper bound on the cover time. : USTCON can be solved by a polynomial time Monte Carlo randomized algorithm with bounded one-sided error, which uses < ...3 KB (468 words) - 10:48, 29 December 2011
- ...st problems in NP (they are [[NP-hardness|NP-hard)]]. People spent lots of time looking for algorithm that finds answers to some NP-complete problem in pol The unsolved problem [[P versus NP|P = NP]] asks whether polynomial time algorithms actually exist for NP-complete, and by corollary, all NP problem ...1 KB (208 words) - 12:39, 30 December 2016
- ...题目中 complete 一词改为 hard。本题需要证明任何一个非空也非<math>\{0,1\}^*</math>的语言在 polynomial-time Karp reduction 下<font color=red><strong>都</strong></font>是 NL-hard，也就是证明<ma ...772 bytes (53 words) - 00:41, 24 October 2019
- ...d in [[Physics]] that says that the amount of something does not change in time. That thing could be as simple as [[mass]] or [[charge]], or something that For a long time, people thought that these laws were true for the amount of mass and [[ener ...3 KB (575 words) - 23:22, 28 November 2015
- ...[[Geiger-Muller detector]] can be used to measure the half-life; it is the time when the activity is half of the original. ...gain, it will be seen that the atom decays within the half life 50% of the time. ...3 KB (407 words) - 04:36, 7 May 2013
- # Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove tha ::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5. ...3 KB (460 words) - 08:16, 25 October 2017
- ...})</math>. The naive algorithm will take asymptotically the same amount of time. ...andomized algorithm, due to Freivalds, running in only <math>O(n^2)</math> time: ...4 KB (694 words) - 03:25, 23 July 2011
- The accelerating electric field reverses just at the time the electrons finish their half circle, so that it accelerates them across ...n a circular path under the influence of a constant magnetic field. If the time to complete one orbit is calculated: ...2 KB (311 words) - 06:34, 12 March 2017
- ...f [[control theory]] to represent a signal that switches on at a specified time and stays switched on indefinitely. It was named after the [[England|Englis The discrete-time unit impulse is the first difference of the discrete-time step ...2 KB (319 words) - 20:50, 20 March 2013
- *"t" is [[time]]. *"n(t)" is the rate of earthquakes in a time after the main shock ...1 KB (210 words) - 13:22, 11 March 2013
- ...e change of velocity [[Division (mathematics)|divide]]d by the change of [[time]]. Acceleration is a [[vector]], and therefore includes both a [[size]] and :<math>t_0</math> is the time at the start ...4 KB (606 words) - 07:19, 25 August 2016
- ...math>Y_t</math> denote the sum of the degrees of all the white vertices at time <math>t</math>. Show that <math>Y_t</math> is a martingale with respect to * Design an efficient, time reversible, ergodic random walk on <math>G</math> whose stationary distribu ...4 KB (631 words) - 04:02, 2 August 2013
- ...ks an action <math>A_t</math> based on a policy <math>\pi</math>. The next time step, the agent receives a reward signal <math>R_{t+1}</math> and a new obs ...3 KB (519 words) - 01:25, 5 April 2017
- ...is used most of the time, for most of the things we can see. Some of the time, for example when the things are too small, classical mechanics is not good #::t is time - how long the object was accelerated for. ...9 KB (1,483 words) - 20:40, 29 October 2016
- ...ath>q</math> be some nonnegative reals with <math>p+q\le 1</math>. At each time step, exactly one of the following occurs. ...stationary distribution is <math>\pi</math>. Prove that the random walk is time-reversible, irreducible, aperiodic, and has stationary distribution <math>\ ...3 KB (555 words) - 12:38, 19 May 2010
- ...on which tells how the concentration of reagents and products changes with time is found. So, a plot of <math>\ln{[A]}</math> against time ''t'' gives a straight line with a slope of <math>-k</math>. ...2 KB (278 words) - 16:34, 20 February 2017
- ...ick lift requires more power. This means the work can be done in a shorter time if there is more power available. :''t'' is [[time]]. ...1 KB (246 words) - 16:49, 16 January 2017
- In this lecture, we are focused on the '''time complexity''', although there are other complexity measures in various comp ...the (worst-case) time complexity of <math>A</math> is the maximum running time over all inputs <math>x</math> of length <math>n</math>. ...11 KB (1,828 words) - 06:00, 27 August 2011
- ...scharge describes how much [[water]] flows through, in a certain amount of time. The amount is usually expressed in <math>\frac{m^3}{s}</math> ([[cubic met ...442 bytes (64 words) - 05:01, 15 March 2017
- |+ Table 1: ''Time taken (in seconds) to answer a simple math question'' ...the largest was 34 seconds. One method we could use to analyze the needed time is to group close numbers together. In order to keep the analysis fair, we' ...3 KB (462 words) - 22:41, 18 October 2014
- *'''Time''': every Thursday, 6:30pm. ...; potential analysis; <br>Knapsack; dynamic programming; pseudo-polynomial time; scale and round; FPTAS.||Chap. 2.6, 3.1 of<br>Williamson-Shmoys. ...4 KB (455 words) - 07:53, 28 December 2011
- ...[convection]]. Usually more than one of these processes happen at the same time. ...conduction''', also known as '''Fourier's law''', means that the rate, in time, of heat transfer through a material is [[Proportionality|proportional]] to ...3 KB (414 words) - 07:43, 16 June 2017
- ...[magnetic energy]]) is no longer [[constant]]. Instead, it decreases with time as [[energy]] is transferred to [[thermal energy]] in the resistance. Becau ...es that <math>U</math> decreases. By differentiating Eq. 1 with respect to time and then substituting the result in Eq. 2, the following is obtained: ...2 KB (282 words) - 23:05, 31 May 2017
- The class '''BPP''' (for Bounded-error Probabilistic Polynomial time) is defined as follows: ...ave a randomized algorithm <math>A</math> running in worst-case polynomial time such that for any input <math>x</math>, ...5 KB (842 words) - 01:10, 30 March 2010
- ...r programming by moving from vertex to vertex of the convex polytope, each time making some progress towards optimizing the objective function. Eventually ...al pivoting rule proposed by Dantzig has an exponentially large worst-case time complexity (though works very good in practice). To-date, it is still unkno ...6 KB (1,029 words) - 09:37, 6 November 2011
- ...calculate the [[frequency]] [[spectrum]] of a [[signal]] that changes over time. This kind of [[signal processing]] has many uses such as [[cryptography]], ...parated. In the audio example above, looking at the signal with respect to time does not make it obvious that the notes A, B, and C are in the signal. Many ...3 KB (471 words) - 16:51, 26 March 2017
- # Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove tha ::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5. ...5 KB (927 words) - 04:53, 12 October 2016
- [[Category:Time]] ...521 bytes (75 words) - 17:34, 20 October 2015
- ...on can be thought of as a picture of how this particle or system acts with time and describes it as fully as possible. ...t positions, energies, velocities or other physical properties at the same time (i.e. "be in two places at once"). However, when one of these properties is ...7 KB (1,105 words) - 21:06, 26 June 2017
- ...aphic]] attack which, like the [[birthday attack]], makes use of a [[space-time tradeoff]]. While the birthday attack attempts to find two values in the do ...ered a time-memory tradeoff that could break the scheme in only double the time to break the single-encryption scheme.<ref>{{cite journal ...3 KB (474 words) - 09:45, 20 October 2014
- ...walk, stationary distribution, convergence of Markov chain, hitting/cover time | ([http://tcs.nju.edu.cn/slides/random2015/MarkovChain.pdf slides]) ...算法 (Fall 2015)/Mixing Time and Coupling|Mixing Time and Coupling]]: mixing time, coupling lemma, coupling of Markov chain, rapid mixing by coupling | ( ...9 KB (893 words) - 12:43, 15 September 2017
- ...walk, stationary distribution, convergence of Markov chain, hitting/cover time ...(Spring 2014)/Mixing Time and Coupling|Mixing Time and Coupling]]: mixing time, coupling lemma, coupling of Markov chain, rapid mixing by coupling ...9 KB (846 words) - 07:34, 2 June 2014
- ...of all possible events, and the probability of them happening at the same time, is needed. For example, to measure mutual information between '''month''' ...coin flip last time will not tell you anything about what will happen next time. ...3 KB (561 words) - 16:37, 28 September 2016
- ...h> is not necessarily regular (every vertex has the same degree). Design a time-reversible lazy random walk which is ergodic and always converges to unifor ...n an arbitrary distribution <math>\pi</math> over <math>V</math>, design a time-reversible lazy random walk which is ergodic and always converges to the st ...3 KB (585 words) - 00:57, 3 June 2014
- ...walk, stationary distribution, convergence of Markov chain, hitting/cover time ...(Spring 2013)/Mixing Time and Coupling|Mixing Time and Coupling]]: mixing time, coupling lemma, coupling of Markov chain, rapid mixing by coupling ...10 KB (1,029 words) - 12:44, 15 September 2017
- ...we introduce a much simpler randomized algorithm which also runs in linear time. ...ath>m</math> of <math>S</math> can be picked from <math>C</math> in linear time. ...10 KB (1,840 words) - 03:10, 19 July 2011
- * Analyze the mixing time of the random walk by coupling. * Prove that the mixing time is <math>O(n\log k)</math>. ...2 KB (345 words) - 06:55, 28 November 2011
- ...this up, we will get to all of the numbers on the table in due time! Each time we hit a rational number that is new for us, we add it to the list of count ...2 KB (379 words) - 14:57, 30 April 2017
- * '''Hitting time''': It takes how long for a random walk to visit some specific vertex. * '''Cover time''': It takes how long for a random walk to visit all vertices. ...4 KB (699 words) - 15:06, 19 July 2011
- * 4.37 years—the amount of time it takes for light from [[Alpha Centauri]] to reach [[Earth]] * 12.27 years—the amount of time [[Nazi Germany]] existed ...5 KB (744 words) - 04:54, 25 January 2014
- ...me from <math>n</math> to 0 and the <math>y</math> power goes up by 1 each time from 0 up to <math>n</math> ...3 KB (420 words) - 21:11, 23 February 2015
- ...</math> elements. We show how to solve this problem with <math>O(1)</math> time by perfect hashing. ...th> elements which answers every search in deterministic <math>O(1)</math> time. ...10 KB (1,895 words) - 06:20, 21 November 2011
- ...proposed to <math>b</math> before he proposed to <math>a</math>, by which time <math>b</math> must either be available or be with a worse man (because her ...''principle of deferred decisions''', each man can be seen as that at each time, sampling a uniformly random woman from the ones who have not already rejec ...3 KB (503 words) - 01:31, 24 July 2011
- #* [[随机算法 (Fall 2011)/Cover Time|Cover Time]] # Coupling and Mixing Time ...12 KB (1,037 words) - 12:45, 15 September 2017
- ...(1)</math> in total variation distance, when <math>d=o(n^{1/2})</math>. If time permits, I will describe how to use this new method to generate uniformly r ...develop a new algorithmic technique that allows to transfer some constant time approximation algorithms for general graphs into random order streaming alg ...7 KB (999 words) - 05:35, 13 July 2017
- ...time in <math>\left(\frac{\text{distance}}{\text{time}}\right)\times\text{time}</math>. This is done by adding small slices of the rate graph together. Th Another time integration is helpful is when finding the [[volume]] of a solid. It can ad ...8 KB (1,358 words) - 13:14, 7 May 2017
- ...s accept the fact that there are at least 11 dimensions in our universe: 1 time dimension and 10 spacial dimensions.) The length of the strings would be de ...924 bytes (133 words) - 17:06, 17 April 2013
- * Analyze the mixing time of the random walk by coupling. * Prove that the mixing time is <math>O(k\log k)</math> by coupling. ...4 KB (682 words) - 19:52, 8 June 2013
- ...ge [[speed]] of the runner if we divide the distance they travelled by the time it took. But this does not say what speed the person was running at exactly ...1.5 seconds. This was a very long and hard process and had to be done each time people wanted to work something out. Imagine a driver trying to figure out ...8 KB (1,490 words) - 13:48, 21 June 2017
- ...he two decks with probability proportional to the size of the deck at that time. :The mixing time of inverse riffle shuffle of a deck of <math>n</math> cards is <math>\tau_{ ...6 KB (991 words) - 13:57, 10 August 2011
- ...f electric resistance present in the conductor, and ''t'' is the amount of time that this happens for. ...878 bytes (132 words) - 00:24, 21 September 2016
- ...'' consists of all decision problems <math>f</math> that have a polynomial time deterministic algorithm <math>V</math> such that for any input <math>x</mat ...have a randomized algorithm <math>A</math> running in expected polynomial time for any input such that for any input <math>x</math>, <math>A(x)=f(x)</math ...4 KB (687 words) - 12:48, 29 March 2010
- *For all <math>i</math>, <math>|H_i|</math> is computable in poly-time. *For any <math>x\in V</math>, it can be determined in poly-time whether <math>x\in H_i</math>. ...8 KB (1,420 words) - 08:29, 19 July 2011
- (3) The <math>\ell_2</math> mixing time of the random walk over <math>n</math> items with distribution <math>\{p^{( ...(v) = \frac{1}{\sqrt{n}}</math>, then show that <math>\ell_2</math> mixing time of <math>\{X_i\}_{i\geq 0}</math> is at least <math>\Omega\left(\frac{\log( ...9 KB (1,507 words) - 10:49, 16 December 2023
- * '''Time period''': Over time, the demand for goods would tend to become more price elastic. For example, ...4 KB (662 words) - 19:51, 22 June 2016
- Topics that I'm considering to cover at next time when I teach this class (perhaps): Feel free to send me an email at any time to tell what topics you would like this class to cover in future. ...12 KB (1,315 words) - 03:37, 18 July 2011
- # Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove tha ::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5. ...5 KB (955 words) - 09:33, 12 November 2019
- # Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove tha ::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5. ...5 KB (979 words) - 11:34, 13 November 2018
- ...ted KMP algorithm inspired by automaton theory runs in <math>O(n+m)</math> time. ...in, uses the idea of fingerprinting and also runs in <math>O(n + m)</math> time. ...9 KB (1,662 words) - 07:05, 15 November 2011
- [[File:Sine waves different frequencies.svg|thumb|250px|As time elapses—here moving left to right on the [[horizontal]] axis—the five [[Sin ...]'''Frequency''' is how often an event repeats itself over a set amount of time. ...3 KB (574 words) - 20:23, 17 June 2016
- ...hat its note value (how long it lasts) does not count as part of the total time value of the [[Bar (music)|measure]]. ...a in small print. This usually means it must be played by taking half the time value of the next note (for example: an appoggiatura in front of a quaver ( ...5 KB (884 words) - 03:12, 18 February 2016
- == Mixing Time == ...ain to approach the stationary distribution. To formally define the mixing time, we need a notion of the distance between two probability distributions. ...27 KB (4,860 words) - 03:17, 22 March 2011
- ...of time, and so that is one way to think of calculus—studying functions of time. There are two different types of calculus. '''Differential calculus''' div ...land and [[Gottfried Leibniz]] in Germany figured out calculus at the same time, working separately from each other. Newton wanted to have a new way to pre ...10 KB (1,680 words) - 20:32, 4 January 2017
- where <math>T</math> is the time (period) of a single rotation(revolution) and <math>f</math> is the frequen If a wheel turns by an angle <math>\theta</math> in a time <math>t</math> then the angular frequency at any moment is given by, ...3 KB (523 words) - 05:12, 16 January 2016
- ...' is the wave function, ''ħ'' is the reduced [[Planck constant]], ''t'' is time, ''x'' is position in space, ''Ĥ'' is a mathematical object known as the '' ...1 KB (187 words) - 14:02, 12 November 2014
- ...example in [[modular arithmetic]]. The algorithm has been known for a long time. It is already written down in a book called ''Chandah-sûtra''. That book ...1 KB (183 words) - 22:13, 8 March 2013
- ...andomized and works in <math>\tilde{O}(mn^{0.9}\log W)</math> total update time under the assumption of oblivious non-adaptive adversary. ...rithm with <math>\tilde{O}((mn^{1/2} + m^{7/5})\log W)</math> total update time, which improves over both previous results when <math>m = O(n^{1.42})</math ...16 KB (900 words) - 04:52, 13 November 2020
- ...andomized and works in <math>\tilde{O}(mn^{0.9}\log W)</math> total update time under the assumption of oblivious non-adaptive adversary. ...rithm with <math>\tilde{O}((mn^{1/2} + m^{7/5})\log W)</math> total update time, which improves over both previous results when <math>m = O(n^{1.42})</math ...16 KB (900 words) - 04:54, 13 November 2020
- ...possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets t This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N< ...12 KB (2,110 words) - 02:55, 19 July 2011
- ...lem, and then give an FPTAS for the problem based on the pseudo-polynomial time algorithm. ...orithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio <math>3/4</math>. ...5 KB (877 words) - 09:10, 22 November 2017
- Algorithms can be written in regular English, but it takes a long time to do so. Instead, algorithms are written in [[pseudocode]], [[Flow chart|f ...hen we write algorithms, we like our algorithm to take the least amount of time so that we can solve our problem as quickly as possible. ...10 KB (1,837 words) - 21:56, 31 August 2017
- ...n</math>, returns the number of perfect matchings in <math>G</math> within time <math>O(n^22^n)</math>. ...2 KB (208 words) - 15:53, 21 October 2019
- * sample uniformly from <math>K</math> in time polynomial of <math>n</math>; * compute its volume <math>\mathrm{vol}(K)</math> precisely in time polynomial of <math>n</math>. ...3 KB (573 words) - 17:09, 31 May 2010
- #<math>\mathcal{M}_c</math> has mixing time <math>O(n\ln n)</math> whenever <math>q\ge\Delta+2</math>. # Random sampling of proper graph colorings can be done in polynomial time whenever <math>q\ge\Delta+1</math>. ...4 KB (712 words) - 06:48, 11 December 2011
- ...[[shape]] in space that is like the [[surface]] of a [[ball]]. Most of the time, the terms ball and sphere are used as the same. But in [[mathematics]], th ...1 KB (190 words) - 09:33, 24 December 2016
- ...riation distance to the stationary distribution monotonically decreases as time passes. Although this is rather intuitive at the first glance, the proof is ...pper bound its mixing time. The coupling technique for bounding the mixing time can be sumerized as follows: ...13 KB (2,540 words) - 13:57, 10 August 2011
- ...f. Philosophically, this can be stated as "nothing depends on time per se (time itself)". Therefore, energy does not vary with time. ...6 KB (881 words) - 09:41, 15 August 2017
- ..., Einstein (1905) drew the conclusion that the concepts of [[space]] and [[time]] needed a fundamental revision. The result was special relativity theory. ...rence that describes time and space homogeneously, isotropically, and in a time-independent manner. Shorthand: space the same everywhere at all times. ...15 KB (2,495 words) - 16:23, 9 April 2017
- Last time we talked about algorithms. Today's topic is '''complexity'''. In this lecture, we are focused on the '''time complexity''', although there are other complexity measures in various comp ...25 KB (4,263 words) - 08:43, 7 June 2010
- ...ative (mathematics)|derivative]], or the rate of change of acceleration by time. Jerk is also called '''jolt''' (in British English), '''surge''', or '''lu ...1 KB (221 words) - 03:01, 24 March 2016
- The time complexity of this sorting algorithm is measured by the '''number of compar ..., sorting which will cost us <math>\Omega(n^2)</math> comparisons, ''every time''! ...16 KB (2,893 words) - 08:43, 7 June 2010
- #include<time.h> gsl_rng_set(r,int(time(NULL))); //设置随机数seed ...7 KB (383 words) - 02:10, 15 December 2010
- Very often such problems were unresolved for centuries. With time, mathematicians came to understand their depth (in some cases), rather tha ...1 KB (214 words) - 03:24, 25 December 2014
- ...hain from an arbitrary state, run the Markov chain for a sufficiently long time, and return the current state. ...iently long time <math>T</math>, and return the current independent set at time <math>T</math>. ...28 KB (4,914 words) - 08:26, 7 June 2010
- ...ether a certain NP complete problem could be solved in quadratic or linear time.<ref>Juris Hartmanis 1989, [http://ecommons.library.cornell.edu/bitstream/1 ...to figure out if the answer is right or wrong, but it may take a very long time for the computer to actually come up with "1, 2, 3, 4, 5" on its own. For s ...15 KB (2,427 words) - 22:24, 16 August 2017
- and the distribution at time <math>t</math> when the initial distribution is <math>q</math>, is given by .../math>. Therefore, we have the following corollary which bounds the mixing time by graph expansion. ...8 KB (1,418 words) - 15:17, 13 December 2011
- = Mixing Time= The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...23 KB (4,166 words) - 05:41, 22 December 2015
- ...e <math>n</math> is the number of vertices, so the algorithm terminates in time <math>O(n^2)</math>. We leave this as an exercise. 1-\Pr[\mbox{failed every time}] &= 1-\Pr[{RandomContract}\mbox{ fails}]^{n(n-1)/2} \\ ...14 KB (2,511 words) - 02:11, 9 October 2015
- * '''Time''': 2015年10月10日 |bgcolor="#A7C1F2" align="center"|'''Time''' ...5 KB (714 words) - 04:34, 17 January 2018
- ...arbitrary]] basis into a friendly basis. Like from our original set, each time we use the process on a new vector, it is guaranteed to be mutually friendl ...1 KB (269 words) - 16:30, 20 April 2015
- 这个结果还有个缺陷，不是最坏时间复杂度O(1)而是amortized time complexity，平摊时间复杂度是O(1)。原因在于FKS的hash function的分配并不平均。 ...还是计算的效率都远远落后与[DHKP97]提出的那个已在在现实中大量应用hash function。因此现实中人们宁愿忍受糟糕的worst-case time complexity，也仍旧使用随机性不够好却可以高效计算的[DHKP97]的hash function。 ...17 KB (967 words) - 06:08, 9 November 2010
- :We design an algorithm with '''''guaranteed''''' worst-case running time, which approximates the optimum within a '''''guaranteed''''' approximation ...re particularly interested in the approximation algorithms running in poly-time of the input size, for the '''NP-hard''' optimization problems. ...20 KB (3,484 words) - 05:14, 11 June 2010
- Now we use the idea of electrical network to analyze the cover time of random walk. Consider an undirected graph <math>G=(V,E)</math>, we const Armed with this theorem, we can now give a better estimation of the cover time of random walk. Let <math>T</math> be a spanning tree of <math>G</math>, an ...5 KB (876 words) - 14:03, 24 December 2011
- ...lem, and then give an FPTAS for the problem based on the pseudo-polynomial time algorithm. ...4 KB (696 words) - 02:57, 21 October 2016
- ...lication algorithm (in theory) is <math>O(n^{2.376})</math>, and so is the time complexity of this method. ...domized algorithm, due to Freivalds, that runs in only <math>O(n^2)</math> time: ...16 KB (2,886 words) - 07:49, 13 November 2011
- ...er a [[domain]] or determining the response of the system over a period of time, the [[independent variable]]s are modulated, while the parameters are held ...m being considered; parameters are dimensionless, or have the dimension of time or its reciprocal." John D. Trimmer, 1950, Response of Physical Systems (Ne ...4 KB (677 words) - 11:57, 25 July 2016
- ...riable <math>X</math> (think that <math>X</math> is a cost such as running time of a randomized algorithm). We call this a '''tail bound''', or a '''tail i ...ed algorithm for a decision problem <math>f</math>, whose expected running time is within <math>T(n)</math> on any input of size <math>n</math>. We transfo ...22 KB (3,809 words) - 05:34, 19 March 2014
- ...uss|Gauss]] in his etude of [[hypergeometric series]] (1813) for the first time rigorously investigated under which conditions a series converged to a limi ...Bolzano]] (''Der binomische Lehrsatz'', Prague 1816, little noticed at the time) and by [[Karl Weierstraß]] in the 1870s. ...4 KB (629 words) - 19:19, 23 January 2015
- ...ted KMP algorithm inspired by automaton theory runs in <math>O(n+m)</math> time. ...in, uses the idea of fingerprinting and also runs in <math>O(n + m)</math> time. ...21 KB (3,794 words) - 09:47, 10 September 2015
- ...mbush]] or military surprise, a military strategy to strike the enemy at a time or place or in a manner for which they are unprepared ...2 KB (242 words) - 12:19, 9 March 2013
- ...e is named after [[Richard Hamming]] who developed it in the 1940s. At the time, Hamming worked with machines that had [[relay]]s and used [[punched card]] ...2 KB (277 words) - 18:18, 3 December 2016
- ...orn clauses true is a [[P-complete]] problem (in fact solvable in [[linear time]]), sometimes called [[Horn-satisfiability|HORNSAT]]. (The unrestricted [[B * Dowling, W. and Gallier, J. (1984), "Linear-time algorithms for testing the satisfiability of propositional Horn formulae". ...5 KB (707 words) - 11:24, 18 May 2013
- ...n the two attached atoms move away and toward the central atom at the same time. ...wo attached atoms do not move away and toward the central atom at the same time. ...8 KB (1,244 words) - 20:31, 26 May 2015
- ...e can start processing jobs at time 0 and can process at most one job at a time. ...e units without interruption. <math>p_j</math> is called the '''processing time''' of job <math>j</math>. ...33 KB (5,832 words) - 15:45, 19 November 2022
- ...e can start processing jobs at time 0 and can process at most one job at a time. ...e units without interruption. <math>p_j</math> is called the '''processing time''' of job <math>j</math>. ...33 KB (5,832 words) - 04:31, 8 November 2021
- Obviously the algorithm runs in polynomial time and always returns a set cover. We will then show how good the set cover r ...\ln n</math> is also the best approximation ratio achievable by polynomial time algorithms, assuming that '''NP'''<math>neq</math>'''P'''. ...33 KB (5,832 words) - 13:15, 25 October 2020
- Obviously the algorithm runs in polynomial time and always returns a set cover. We will then show how good the set cover r ...\ln n</math> is also the best approximation ratio achievable by polynomial time algorithms, assuming that '''NP'''<math>neq</math>'''P'''. ...33 KB (5,832 words) - 05:22, 29 October 2019
- Obviously the algorithm runs in polynomial time and always returns a set cover. We will then show how good the set cover r ...\ln n</math> is also the best approximation ratio achievable by polynomial time algorithms, assuming that '''NP'''<math>neq</math>'''P'''. ...33 KB (5,832 words) - 07:54, 31 October 2018
- Obviously the algorithm runs in polynomial time and always returns a set cover. We will then show how good the set cover r ...\ln n</math> is also the best approximation ratio achievable by polynomial time algorithms, assuming that '''NP'''<math>neq</math>'''P'''. ...33 KB (5,832 words) - 06:23, 29 September 2016
- Obviously the algorithm runs in polynomial time and always returns a set cover. We will then show how good the set cover r ...\ln n</math> is also the best approximation ratio achievable by polynomial time algorithms, assuming that '''NP'''<math>neq</math>'''P'''. ...33 KB (5,832 words) - 03:44, 27 October 2017
- ...G_0(z)</math> and <math>G_1(z)</math>. Reconstruction filters are given by time reversal analysis filters. ...2 KB (299 words) - 08:12, 11 June 2013
- = Mixing Time= The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...27 KB (4,881 words) - 13:52, 31 July 2013
- = Mixing Time= The '''mixing time''' of a Markov chain gives the rate at which a Markov chain converges to th ...27 KB (4,881 words) - 07:04, 2 June 2014
- ...ve proposed to <math>b</math> before proposing to <math>a</math>, by which time <math>b</math> must either be single or be matched to a man ranked lower th ...cision of random choice in the random input can be deferred to the running time of the algorithm. ...24 KB (4,172 words) - 15:38, 19 March 2013
- <math>dt</math> is the change in time, measured in [[second]]s. ...2 KB (281 words) - 23:25, 2 August 2017
- ...a '''state''', as <math>X_t</math> represents the state of the process at time <math>t</math>. ;discrete time ...29 KB (4,888 words) - 09:13, 16 December 2011
- ...</math>. This law also gives rise to an uncertainty between [[energy]] and time, which can be expressed in the same way as the relation between momentum an ...This implies that a particle occupies more than one position ''at the same time.'' In other words, a particle exists in at least two different positions si ...5 KB (859 words) - 07:03, 27 February 2017
- ...lication algorithm (in theory) is <math>O(n^{2.376})</math>, and so is the time complexity of this method. ...domized algorithm, due to Freivalds, that runs in only <math>O(n^2)</math> time: ...20 KB (3,617 words) - 01:24, 8 June 2010
- ...t''' constructions of expander graphs. In particular, we need a polynomial time '''deterministic''' algorithm which given a vertex <math>v</math> and a int ...fact that <math>G</math> is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the <math>\phi(G)</ ...35 KB (6,195 words) - 08:39, 7 June 2010
- * Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is <ma ...orithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio <math>3/4</math>. ...5 KB (915 words) - 12:59, 10 December 2020
- ...sed to try to correct for this.<ref>James R. Bence 1995. Analysis of short time series: correcting for autocorrelation. ''Ecology'' '''76'''(2): 628–639.</ ...9 KB (1,463 words) - 03:47, 2 July 2016
- ...rp-P-complete '''#P-complete''']. So we do not expect to have a polynomial-time algorithm for exact solving the problem. Instead we are seeking for approxi {{Theorem|FPTAS (Fully Polynomial-Time Approximation Scheme)| ...23 KB (4,076 words) - 15:50, 12 May 2014
- ...andomized and works in <math>\tilde{O}(mn^{0.9}\log W)</math> total update time under the assumption of oblivious non-adaptive adversary. ...rithm with <math>\tilde{O}((mn^{1/2} + m^{7/5})\log W)</math> total update time, which improves over both previous results when <math>m = O(n^{1.42})</math ...20 KB (1,328 words) - 14:52, 20 November 2020
- ...\phi(x,y,z)</math>. We will assume that the temperature does not change in time. Then, at each point in the room, the gradient at that point will show the ...2 KB (376 words) - 23:39, 8 March 2013
- [[Image:Clock group.svg|thumb|right|Time-keeping on a clock gives an example of modular arithmetic.]] ...2 KB (332 words) - 07:26, 9 March 2015
- ...riable <math>X</math> (think that <math>X</math> is a cost such as running time of a randomized algorithm). We call this a '''tail bound''', or a '''tail i ...ed algorithm for a decision problem <math>f</math>, whose expected running time is within <math>T(n)</math> on any input of size <math>n</math>. We transfo ...30 KB (5,292 words) - 07:49, 3 August 2011
- ...n</math>, returns the number of perfect matchings in <math>G</math> within time <math>n 2^{O(n)}</math>. ...4 KB (352 words) - 12:01, 15 October 2017
- ...a '''state''', as <math>X_t</math> represents the state of the process at time <math>t</math>. ;discrete time ...37 KB (6,516 words) - 08:40, 7 June 2010
- The time complexity of this sorting algorithm is measured by the '''number of compar ...from a fixed position (e.g. the first number in the array). The worst-case time complexity in terms of number of comparisons is <math>\Theta(n^2)</math>. ...7 KB (1,276 words) - 06:03, 27 August 2011
- ...t cell-probe lower bound: spending <math>o(\log n)</math> (even amortized) time per operation results in at best an <math>\exp(-\delta^2 n)</math> probabil ...on of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation g ...14 KB (1,850 words) - 01:51, 7 May 2018
- ...possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets t This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N< ...17 KB (3,066 words) - 06:06, 18 April 2013
- ...feel that you are not contributing enough to your group, then try to spend time thinking about the problems alone before working with your group. If you en ...ccomodate late submission requests ONLY IF you made such requests ahead of time. ...6 KB (652 words) - 07:10, 27 April 2024
- ...riable <math>X</math> (think that <math>X</math> is a cost such as running time of a randomized algorithm). We call this a '''tail bound''', or a '''tail i ...ed algorithm for a decision problem <math>f</math>, whose expected running time is within <math>T(n)</math> on any input of size <math>n</math>. We transfo ...29 KB (5,238 words) - 05:34, 13 November 2015
- Cuckoo hashing also achieves constant search time on a linear space, and after acquiring the hash functions, the accesses to ...2 KB (397 words) - 09:08, 13 November 2011
- ...n</math>, returns the number of perfect matchings in <math>G</math> within time <math>n 2^{O(n)}</math>. ...3 KB (374 words) - 14:36, 27 September 2016
- ...a '''state''', as <math>X_t</math> represents the state of the process at time <math>t</math>. ;discrete time ...40 KB (7,046 words) - 10:00, 13 December 2015
- ...a '''state''', as <math>X_t</math> represents the state of the process at time <math>t</math>. ;discrete time ...40 KB (7,046 words) - 08:04, 2 June 2014
- ...a '''state''', as <math>X_t</math> represents the state of the process at time <math>t</math>. ;discrete time ...40 KB (7,049 words) - 15:11, 8 June 2013
- ...) discovered the same thing independently. They invented it about the same time.)<ref>{{cite web | title = A Princeton Companion | url = http://etcweb.prin ...2 KB (365 words) - 13:00, 25 September 2014
- ...d random walks''': Markov chians, random walks, hitting/cover time, mixing time, coupling, conductance. ...behavior of the algorithm is random. To be specific, the output or running time of the algorithm may be random. ...22 KB (3,591 words) - 03:54, 17 February 2014
- ...d random walks''': Markov chians, random walks, hitting/cover time, mixing time, coupling, conductance. ...behavior of the algorithm is random. To be specific, the output or running time of the algorithm may be random. ...22 KB (3,591 words) - 10:45, 4 March 2013
- ...ellipseconstr.htm Ellipse Construction] - Another interactive sketch, this time showing a different method of tracing the ellipse. (Requires Java.) ...3 KB (417 words) - 09:17, 7 November 2013
- [[File: matrix_multiplication.png|thumb|360px|right|The evolution of time complexity <math>O(n^{\omega})</math> for matrix multiplication.]] ...ath>O(n^3)</math> time, assuming that each arithmetic operation takes unit time. ...28 KB (5,169 words) - 11:26, 13 September 2015
- 停时 (stopping time) 的概念如下定义。 ...>T</math> 是一个关于离散时间随机过程 <math>\{X_n:n\ge 0\}</math> 的'''停时''' ('''stopping time''')，若对于任意 <math>n\ge 0</math>，事件 <math>T=n</math> 发生与否都取决于 <math>X_0,X_1,\l ...18 KB (2,077 words) - 08:07, 5 June 2023
- The time complexity of this sorting algorithm is measured by the '''number of compar ...<math>i</math> (e.g. the first element <math>\pi_0</math>). The worst-case time complexity in terms of number of comparisons is <math>\Theta(n^2)</math>, t ...29 KB (4,994 words) - 01:21, 29 August 2011
- ...nts <math>x_1,x_2,\ldots,x_n</math> is presented to the algorithm one at a time, where the size of data <math>n</math> is unknown to the algorithm. The alg * '''time cost''': time complexity of answering each query by accessing to the data structure. ...25 KB (4,512 words) - 05:52, 16 September 2019
- ...nts <math>x_1,x_2,\ldots,x_n</math> is presented to the algorithm one at a time, where the size of data <math>n</math> is unknown to the algorithm. The alg * '''time cost''': time complexity of answering each query by accessing to the data structure. ...25 KB (4,512 words) - 07:51, 29 September 2020
- ...nts <math>x_1,x_2,\ldots,x_n</math> is presented to the algorithm one at a time, where the size of data <math>n</math> is unknown to the algorithm. The alg * '''time cost''': time complexity of answering each query by accessing to the data structure. ...25 KB (4,512 words) - 15:48, 3 October 2022
- ...nts <math>x_1,x_2,\ldots,x_n</math> is presented to the algorithm one at a time, where the size of data <math>n</math> is unknown to the algorithm. The alg * '''time cost''': time complexity of answering each query by accessing to the data structure. ...25 KB (4,512 words) - 09:09, 20 September 2018
- ...nts <math>x_1,x_2,\ldots,x_n</math> is presented to the algorithm one at a time, where the size of data <math>n</math> is unknown to the algorithm. The alg * '''time cost''': time complexity of answering each query by accessing to the data structure. ...25 KB (4,512 words) - 06:13, 9 September 2021
- ...he homework are the monthly mean data from NCEP-DOE Reanalysis 2, with the time span from 1979/1 to 2009/12. For more info on the dataset, please go to the ...3 KB (448 words) - 02:40, 20 March 2024
- The acceleration {{math|'''a'''}} of a particle is the time derivative of its velocity {{math|'''v'''}}: ...{{math|''m''}}, the net force {{math|'''F'''}} on the particle is equal to time derivative of the particle's momentum {{math|'''p'''}}:<ref name= taylor /> ...7 KB (1,154 words) - 07:21, 16 August 2017
- ...ted with a vertex may be the distance between two cities, or the amount of time it takes to travel between the two. ...3 KB (488 words) - 18:43, 22 August 2017
- ...ss evolving through time, where <math>X_i</math> gives some measurement at time <math>i</math>, the bounded difference condition states that the process do ...9 KB (1,575 words) - 03:03, 19 July 2011
- If the force is weak and the object is heavy, then it will take a long time to increase the speed very much, ...3 KB (548 words) - 15:02, 5 April 2017
- ...], \ldots, A[n]</math>, which is passed to your algorithm by one item at a time in the sequential order. (Equivalently, you can imagine that your algorithm ...3 KB (443 words) - 01:40, 19 September 2011
- ...sier to use the "summary" than having to use the whole set of data all the time. Summarizing the data also allows to find common [[pattern]]s. In statistic Statistics have been in use for a long time. The first known statistics are [[census]] data. The [[Babylonia]]ns did a ...10 KB (1,630 words) - 17:19, 10 February 2017
- ...etting an exact solution is impractical though, because it requires a long time, or many resources. An example for this is calculating [[Power series]]. ...3 KB (411 words) - 18:21, 12 March 2013
- ...ames_conjecture unique game conjecture (UGC)], there does not exist a poly-time algorithm with better approximation ratio unless <math>P=NP</math>. ...his gives us a deterministic polynomial time (actually <math>O(n^2)</math> time) <math>1/2</math>-approximation algorithm. ...31 KB (5,704 words) - 08:39, 5 May 2014
- ...ames_conjecture unique game conjecture (UGC)], there does not exist a poly-time algorithm with better approximation ratio unless <math>P=NP</math>. ...his gives us a deterministic polynomial time (actually <math>O(n^2)</math> time) <math>1/2</math>-approximation algorithm. ...31 KB (5,704 words) - 05:36, 13 November 2015
- ...fact that <math>G</math> is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the <math>\phi(G)</ ...cally more interesting and also more useful to us for analyzing the mixing time of random walks. ...37 KB (6,824 words) - 02:20, 29 December 2015
- ...ineering]] and [[computer programming]] are areas that use algebra all the time. It is also useful to know in [[surveying]], [[construction]] and [[busine ...r. The number that is made is called the "dependent" variable. Most of the time the independent variable is written as ''x'' and the dependent variable is ...13 KB (2,204 words) - 07:13, 30 July 2017
- ...e <math>n</math> is the number of vertices, so the algorithm terminates in time <math>O(n^2)</math>. We leave this as an exercise. 1-\Pr[\mbox{failed every time}] &= 1-\Pr[{RandomContract}\mbox{ fails}]^{n(n-1)/2} \\ ...26 KB (4,800 words) - 06:38, 3 March 2014
- ...rticular instant) is defined as the derivative of the velocity function of time. For example, if an objects position on a line is given by v(t)=-16t<sup>2< ...3 KB (540 words) - 21:28, 10 August 2014
- ...math> is in '''NP''' if there exist a polynomial <math>p</math> and a poly-time algorithm <math>V</math> with boolean output such that for every <math>x\in ...only if there ''exists'' a '''certificate''' which can be verified in poly-time. ...37 KB (6,579 words) - 08:26, 7 June 2010
- ...ium is an idea which describes the behavior of [[chemical reaction]]s over time. In reactions that have finished reacting and have attained equlibrium, the ...3 KB (541 words) - 12:47, 13 December 2016
- ...or, Ontario]] (The [[resident]]s of Windsor would not have known it at the time, since the humidex had yet to be [[invention|invent]]ed). ...3 KB (442 words) - 03:45, 27 July 2013
- [[File: matrix_multiplication.png|thumb|360px|right|The evolution of time complexity <math>O(n^{\omega})</math> for matrix multiplication.]] ...ath>O(n^3)</math> time, assuming that each arithmetic operation takes unit time. ...37 KB (6,665 words) - 12:21, 19 September 2023
- ...e an [[electric field]]. If two fields exist in the same space at the same time, then the two fields exert (~ put) force on each other. The force they make ...3 KB (522 words) - 15:04, 17 March 2017
- * Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is <ma ...orithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio <math>3/4</math>. ...7 KB (1,218 words) - 07:41, 24 December 2022
- ...possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets t This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N< ...27 KB (4,865 words) - 07:47, 24 March 2014
- ...possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets t This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N< ...27 KB (4,865 words) - 08:14, 24 March 2014
- ...e root of −9 is not −3. This is because −3 x −3 = +9, not −9. For a long time it seemed as though there was no answer to the square root of −9. ...3 KB (567 words) - 22:50, 3 February 2016
- ...could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is <math>[n]</math>. Let <math>X_i</math> be t ...10 KB (1,940 words) - 03:37, 19 October 2021
- ...could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is <math>[n]</math>. Let <math>X_i</math> be t ...10 KB (1,940 words) - 22:39, 15 September 2020
- ...could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is <math>[n]</math>. Let <math>X_i</math> be t ...10 KB (1,940 words) - 07:38, 14 October 2019
- ...could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is <math>[n]</math>. Let <math>X_i</math> be t ...10 KB (1,940 words) - 10:53, 10 October 2023
- ...could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is <math>[n]</math>. Let <math>X_i</math> be t ...10 KB (1,940 words) - 12:53, 11 October 2022
- ...s not depend on its volume, or position in space, for instance. For a long time (at least since the works of [[Antoine Lavoisier]] in the second half of th ...3 KB (496 words) - 11:10, 5 July 2017
- ...e is little [[friction]] (good bearings) then it will keep rotating a long time. When energy is needed, it can be taken from the wheel again. So it is a si ...3 KB (525 words) - 22:13, 8 March 2013
- ::<math>\Delta t</math> is the change in time ...3 KB (536 words) - 13:33, 9 April 2017
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,705 words) - 07:31, 5 September 2022
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,705 words) - 08:44, 24 August 2021
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,705 words) - 11:24, 8 September 2020
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,705 words) - 05:26, 16 September 2019
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,708 words) - 10:34, 12 September 2023
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,745 words) - 01:16, 10 September 2018
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,673 words) - 09:03, 22 September 2016
- ...ansversal of <math>\{S_1, S_2, \cdots, S_r\}</math> in expected polynomial time. ...3 KB (622 words) - 11:08, 22 December 2020
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...43 KB (7,750 words) - 15:39, 15 September 2017
- ...:5080/realtime/main_page.html Mesoscale Compressible Community (MC2)] Real-Time Model Predictions''". (Potential vorticity analysis) ...4 KB (495 words) - 19:17, 27 May 2017
- ...perbola. On a [[sundial]], the path followed by the tip of the shadow over time is a hyperbola. ...3 KB (573 words) - 16:29, 22 February 2015
- ...d function in letters between them so the modern concept began at the same time as calculus. ...4 KB (751 words) - 09:24, 21 January 2017
- ...fact that <math>G</math> is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the <math>\phi(G)</ ...cally more interesting and also more useful to us for analyzing the mixing time of random walks. ...41 KB (7,547 words) - 09:24, 22 May 2023
- ...(<math>\phi</math>) finds a satisfying assignment for <math>\phi</math> in time <math>O(n+km\log m)</math> with high probability. ...math> which is much shorter than <math>r</math>, then we prove the running time of the algorithm <math>\mathsf{Alg}(r, \phi)</math> cannot be too long. ...31 KB (5,614 words) - 12:29, 8 December 2015
- ...n]] [[Blaise Pascal]], but it was used in [[China]] 3 centuries before his time. ...5 KB (707 words) - 07:38, 14 December 2015
- ...torical reasons (in ''human'' history), the [[Planck length]] and [[Planck time]] are conceptually linked at a fundamental physical level. ...4 KB (570 words) - 21:33, 20 October 2014
- ...ames_conjecture unique game conjecture (UGC)], there does not exist a poly-time algorithm with better approximation ratio unless <math>P=NP</math>. ...his gives us a deterministic polynomial time (actually <math>O(n^2)</math> time) <math>1/2</math>-approximation algorithm. ...39 KB (7,106 words) - 09:54, 24 May 2013
- :Eigenvalues and mixing time. ...//pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf Markov chain and mixing time] ...21 KB (2,460 words) - 17:28, 7 March 2023
- ...extensive use of new materials and manufacturing methods developed at the time. ===Time line=== ...15 KB (2,242 words) - 18:49, 30 May 2017
- Trying to know ahead of time which teams will win may include looking at the standard deviations of the ...his information can be used to help understand how a driver can reduce the time to finish a lap. ...12 KB (1,881 words) - 09:42, 29 May 2017
- ...possible that more than one packets want to use the same edge at the same time. We assume that a queue is associated to each edge, such that the packets t This is pretty bad, because we expect that the routing time is comparable to the diameter of the network, which is only <math>d=\log N< ...31 KB (5,481 words) - 03:52, 9 November 2010
- ...assignment of <math>m</math> variables takes <math>m</math> bits, and each time of calling '''Fix''' takes <math>k</math> bits. ...ha>0</math>. In fact, in this case, <math>t=O(n\log n)</math>, the running time of the procedure is bounded by a polynomial! ...16 KB (2,926 words) - 04:01, 24 July 2011
- ...ve proposed to <math>b</math> before proposing to <math>a</math>, by which time <math>b</math> must either be single or be matched to a man ranked lower th ...cision of random choice in the random input can be deferred to the running time of the algorithm. ...38 KB (6,912 words) - 15:45, 3 October 2022
- At the time, [[science]] and [[engineering]] were viewed differently than today. Mathem ...3 KB (510 words) - 23:40, 14 March 2017
- ...lues of each variable that will make all of the equations true at the same time. If no such values can satisfy all of the equations in the system, then the ...10 KB (1,386 words) - 15:51, 19 June 2016
- ...</math> elements. We show how to solve this problem with <math>O(1)</math> time by perfect hashing. ...th> elements which answers every search in deterministic <math>O(1)</math> time. ...37 KB (6,743 words) - 09:07, 13 November 2011
- ...anks 5 and 6, because in this pair, the runner from Group B had the faster time. By the Kerby simple difference formula, 95% of the data support the hypot ...4 KB (546 words) - 20:04, 12 February 2016
- ...> are written out explicitly, the question is trivially answered in linear time just by comparing their coefficients. But in practice they are usually give ...4 KB (762 words) - 07:05, 15 November 2011
- * '''time cost''': time complexity of answering each query by accessing to the data structure. ...balanced search tree''': with space cost <math>O(n\log N)</math> bits and time cost <math>O(\log n)</math>. ...48 KB (8,716 words) - 08:15, 15 October 2023
- ...ble sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices. ...hm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting ...49 KB (8,708 words) - 08:53, 14 September 2023
- ...Then, in order to probe the growth of quantum pseudorandomness during the time-evolutions, we propose the idea of using the system’s multiple-quantum cohe ...asurements. I will also talk about its applications: (i) a quasipolynomial-time algorithm which detects multipartite entanglement with amount larger than a ...24 KB (1,651 words) - 02:56, 12 March 2024
- ...m can come from [[cardiac arrest]]. When Chloroform is stored for a longer time period, it can decay into [[Phosgene]]. Phosgene was a [[chemical weapon]] ...4 KB (513 words) - 07:29, 5 October 2015
- ...could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is <math>[n]</math>. Let <math>X_i</math> be t ...'s inequality. We also work on the sum of the martingale differences (this time the differences are <math>(Y_i-Y_{i-1})</math>), yet conditioning on <math> ...20 KB (3,641 words) - 03:06, 19 July 2011
- ...olecule that absorb light in this UV-Visible region. They are most of the time characterized by delocalized pi electrons. Pi electrons refer to a type of ...5 KB (697 words) - 16:44, 23 February 2015
- The time complexity of this sorting algorithm is measured by the '''number of compar ...from a fixed position (e.g. the first number in the array). The worst-case time complexity in terms of number of comparisons is <math>\Theta(n^2)</math>. ...19 KB (3,431 words) - 06:53, 14 April 2014
- ...</math> elements. We show how to solve this problem with <math>O(1)</math> time by perfect hashing. ...th> elements which answers every search in deterministic <math>O(1)</math> time. ...42 KB (7,662 words) - 08:41, 7 June 2010
- ...recursion to calculate Fibonacci numbers, which can take a computer a long time to do. ...4 KB (560 words) - 16:16, 13 July 2017
- ...c x)</math> directly. However, there exists an oracle <math>O</math>, each time <math>O</math> gets an input <math>\vec x</math>, it immediately outputs th ...4 KB (721 words) - 09:38, 14 September 2021
- ...ames_conjecture unique game conjecture (UGC)], there does not exist a poly-time algorithm with better approximation ratio unless <math>P=NP</math>. ...his gives us a deterministic polynomial time (actually <math>O(n^2)</math> time) <math>1/2</math>-approximation algorithm. ...18 KB (3,232 words) - 07:32, 21 November 2011
- # Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove tha ::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5. ...11 KB (1,851 words) - 14:57, 3 November 2020
- ...v<sub>e</sub> with a line over it (a electron antineutrino). "t" refers to time.]] ...4 KB (754 words) - 04:34, 20 August 2017
- ...leaving group can remain close to the carbocation intermediate for a short time and [[wikt:block|block]] nucleophilic attack. This is very different than ...[[hydroxide]] or [[methoxide]] ion, the alkene will again be formed, this time via an [[Elimination reaction#E2 mechanism|E2 elimination]]. This will be ...10 KB (1,372 words) - 12:07, 20 March 2013
- ...ss evolving through time, where <math>X_i</math> gives some measurement at time <math>i</math>, the bounded difference condition states that the process do ...could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is <math>[n]</math>. Let <math>X_i</math> be t ...25 KB (4,555 words) - 08:25, 31 March 2014
- ...s towards ever more negative total potential energy. This cosmic flow is [[time]]. ...ll (spherical) space''', remaining nearly balanced for an exceedingly long time until its inherent instability prevails. We shall see later that the densit ...23 KB (3,626 words) - 09:52, 1 September 2017
- ...''Evolution''. 2nd ed, Blackwell p598. ISBN 0-86542-495-0</ref> Changes in time of development in an evolutionary series or clade are very common. The tren ...4 KB (585 words) - 20:57, 12 March 2013
- ...ansversal of <math>\{S_1, S_2, \cdots, S_r\}</math> in expected polynomial time. ...5 KB (817 words) - 13:20, 23 December 2019
- ...umber ''e''. If the bank pays interest more often, so the amount paid each time is less, then the number will be closer to the number ''e''. ...5 KB (766 words) - 22:24, 8 February 2015
- ...fact that <math>G</math> is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the <math>\phi(G)</ ...cally more interesting and also more useful to us for analyzing the mixing time of random walks. ...34 KB (6,244 words) - 15:28, 8 June 2013
- ...ansversal of <math>\{S_1, S_2, \cdots, S_r\}</math> in expected polynomial time. ...5 KB (797 words) - 14:36, 31 October 2022
- ...a resistor, both the voltage and the current goes up and down at the same time, they are said to be in phase, but with an impedance it's different, the vo ...5 KB (850 words) - 06:03, 26 June 2016
- .... Another scale is the "short scale" under which a new name is given every time a number is a thousand times larger than the last named number. This scale ...14 KB (2,057 words) - 01:36, 21 August 2017
- ...domized rounding process if there remains some uncovered subsets after one time of applying the randomized rounding.) ...4 KB (767 words) - 09:36, 5 May 2014