Search results

Create the page "Linear time" on this wiki! See also the search results found.

• Computational geometry
  describe any point in our space. Most of the time, we will be using the Cartesian (rectangular) coordinate otherwise do something else. This is a time-consuming and error-prone way of
  83 KB (14,390 words) - 06:14, 11 April 2014
• Depth-first search
  ===Time=== ...es DFS <math>\mathcal{O}(E+V)</math> overall, [[Asymptotic analysis|linear time]], which, like [[Breadth-first search|BFS]], is asymptotically optimal for
  17 KB (2,930 words) - 00:28, 3 March 2012
• Breadth-first search
  ...r, precisely specified (yet important) problem, solves it well (in minimal time and space), and is easy to understand and to implement. ===Time===
  6 KB (1,030 words) - 23:33, 11 March 2011
• Queue
  ...make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment a
  6 KB (1,081 words) - 04:48, 5 March 2011
• Deque
  ...make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment a
  9 KB (1,494 words) - 03:35, 4 March 2011
• Kruskal's algorithm
  ...le implementations of Kruskal's algorithm whose running times are close to linear, usually outperforming [[Prim's algorithm]] in sparse graphs. ...haracterized as a [[greedy algorithm]], which builds the MST one edge at a time. As befits a MST algorithm, the greedy strategy is to continually add the r
  8 KB (1,403 words) - 05:47, 31 May 2011
• Heavy-light decomposition
  ...the endpoints of a path, with degree one) that gives important asymptotic time bounds for certain problems involving trees. It appears to have been introd ...on each of these, so overall this "skipping" operation runs in logarithmic time.
  9 KB (1,665 words) - 12:40, 6 August 2015
• Segment tree
  ...igned to answer the range minimum query without explicitly re-stating each time that we are doing so. Bear in mind, however, that other types of segment tr ===Time===
  21 KB (3,669 words) - 02:34, 6 April 2016
• Convex hull trick
  ...o determine ''efficiently'', after preprocessing, which member of a set of linear functions in one variable attains an extremal value for a given value of th ...nimum value of <math>y</math> that can be obtained if we select one of the linear functions and evaluate it at <math>x</math>. For example, suppose our funct
  19 KB (3,419 words) - 02:24, 13 September 2023
• Convex hull
  .... Initially we will face the right (increasing x-coordinate). At any given time we maintain both a point <math>P</math> (our location) and a [[Computationa ...points that are actually on the hull, denoted <math>h</math>, so the total time taken is <math>O(nh)</math>. In the worst case, in which <math>h=n</math> a
  18 KB (3,180 words) - 05:49, 31 May 2011
• Optimization
  ...optimization can also mean reducing disk seeks, cache faults, or response time, or increasing throughput. A specific concept that optimizes a program, suc ...timizations that do not affect asymptotic (scaling) behaviour, but improve time or memory usage by a constant factor only, see [[invisible constant factor]
  7 KB (1,155 words) - 01:34, 5 January 2012
• Longest palindromic substring
  ...h>. We now show that the problem can be solved in <math>O(N \log N)</math> time using standard data structures from the literature, the [[suffix tree]] and ..., '''as''', '''bananas''', '''nanas''', '''nas''', '''s''']. Simple linear-time algorithms now exist for computation of suffix arrays of strings with const
  19 KB (3,066 words) - 10:05, 1 November 2016
• String
  ...characters from the same alphabet can be compared for equality in constant time. ...alphabets as follows<ref>Juha Kärkkäinen and Peter Sanders. 2003. Simple linear work suffix array construction. In ''Proceedings of the 30th international
  12 KB (1,959 words) - 23:56, 23 November 2011
• Disjoint sets
  ...ust look up its representative in the table, which takes <math>O(1)</math> time. When we have to unite two sets, however, we have to pick one of these two ...ibed above supports <math>O(1)</math> find, but requires <math>O(N)</math> time for union'. What if we focus on trying to improving the speed of the union
  13 KB (2,270 words) - 01:29, 11 December 2011
• Array
  ...dex of <math>n-1</math>, we can access any object in the array in constant time just by knowing the index (using the formula for the <math>i</math><sup>th< ...sses themselves, which can be cumbersome to work with and may change every time a program is run and memory for the array allocated. If an element of an ar
  17 KB (2,904 words) - 03:08, 17 April 2012
• Graph theory
  ...ngth of time it takes to traverse the corresponding highway (''i.e.'', the time between the two cities corresponding to the vertices that the edge connects ...of a graph in which the relationships may involve more than two nodes at a time. They are generally less useful than ordinary graphs.
  25 KB (4,451 words) - 23:15, 19 October 2020
• Topological sort
  ...atrix or an adjacency list. Nor will we scan through the entire graph each time step 2 is executed in order to find a source; this, too, is computationally ...is popped). Overall, then, this algorithm takes <math>O(E+V)</math> time (linear).
  9 KB (1,677 words) - 11:36, 25 January 2012
• Longest common substring
  ...ry(ies) common to both strings. This, however, gives <math>O(n^3+m)</math> time (assuming we have two strings of lengths <math>n</math> and <math>m</math> We shall see that all three variations can be solved in linear time, no matter how many strings are given in input.
  7 KB (1,242 words) - 04:49, 29 May 2011
• Algorithm
  ...n instance of a problem is more efficient than a program that takes a long time and uses lots of memory. The technique of ''asymptotic analysis'' is genera ...to search for genes in the human genome. Using a naive <math>O(nm)</math> time algorithm for [[string searching]], approximately 10¹⁴ operation
  10 KB (1,628 words) - 18:12, 28 June 2011
• Naive algorithm
  ...irable level of [[Analysis of algorithms|efficiency]] (usually in terms of time, but also possibly memory) despite finding a correct solution or it does no ...ow needles to be "looked up" in the haystack rather than searched for in a linear fashion leads to the [[suffix tree]] data structure which reduces string se
  2 KB (297 words) - 15:24, 29 June 2011
• String searching
  ...e number of matches found for the needle in the haystack), which is linear time. ...ear-time algorithm, as it will use <math>O(m + n_1 + m + n_2 + ...)</math> time, which is the same as <math>O(n_1 + n_2 + ...)</math> since the needle is n
  16 KB (2,766 words) - 19:54, 6 April 2011
• Knuth–Morris–Pratt algorithm
  ...Together with linear time preprocessing of the needle, this gives a linear time algorithm overall. ...'', occupies linear space, and, as we shall see, can be computed in linear time. It contains ''all'' the information we need in order to execute the "smart
  18 KB (3,295 words) - 22:01, 11 December 2011
• Rabin–Karp algorithm
  ...thm, which simply assumes all probable matches are correct, guaranteeing a linear runtime but with a small probability of false positives. ...al to the length of the needle. (In general, equality comparisons may take time proportional to the amount of data being compared. Hence, a CPU can often c
  9 KB (1,664 words) - 16:33, 29 May 2011
• Sliding range minimum query
  ...pecial case is important because it can be solved in linear time (that is, linear in the size of the array plus the number of query intervals) and requires n ...'remove'' in logarithmic time and ''query'' in constant time. This gives a time bound of <math>O(N \log N + Q)</math> where <math>N</math> is the size of t
  5 KB (938 words) - 21:33, 4 April 2021
• Map
  ..., ''Search'', ''Delete'', and ''Change'' have a worst-case time complexity linear in the size of the list, as they may have to examine all of its elements, w [[Skip list]]s are not often used in practice, but offer the same time complexity guarantees as BBSTs and are efficient with space as well.
  13 KB (2,270 words) - 18:16, 25 February 2012
• All nearest smaller values
  ...we do a linear scan on each element, we get a trivial <math>O(n^2)</math> time solution to ANSV. However, it turns out that there is a simple linear time (<math>O(n)</math>) solution to ANSV, which is clearly asymptotically optim
  4 KB (826 words) - 14:12, 2 January 2018
• Range minimum query
  ...range given and selecting the minimum element, which can take up to linear time. The problem is interesting because we often desire to answer a large numbe This problem can be solved in linear time in the special case in which the intervals are guaranteed to be given in su
  14 KB (2,606 words) - 16:46, 24 April 2014
• Lowest common ancestor
  ...s approach will actually perform quite well (around <math>O(\log N)</math> time per query, where <math>N</math> is the size of the tree). ...> time (that is, linear)<ref>Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", ''Proceedings of the 1
  11 KB (2,023 words) - 23:03, 5 April 2016
• Cartesian tree
  The naive method described above may take up to <math>O(N^2)</math> time, since it requires scanning the sequence to find its minimum, then scanning This is true just before the loop runs for the first time (<math>m = 0</math>), because we will have a singleton tree that contains j
  17 KB (3,062 words) - 18:02, 13 June 2016
• Prefix sum array and difference array
  We see that the difference array can be computed in [[linear time]] from the original array, and is shorter than the original array by one el ..., 18, 18, 25]</math>. Computing the prefix sum array can be done in linear time as well, and the prefix sum array is longer than the original array by one
  25 KB (4,594 words) - 23:35, 19 December 2023
• Hidden constant factor
  When the time or space required for an [[algorithm]] is expressed in terms of the input s ...always design a faster machine, which would make our algorithms take less time to run, but that wouldn't reflect the efficiency of the algorithm itself; a
  4 KB (675 words) - 08:49, 18 February 2012
• Asymptotic analysis
  ...refers to the fact that this form of analysis neglects the exact amount of time or memory that the algorithm uses on specific cases, but is concerned only ...mn, the execution time of Alice's program in the second, and the execution time of Bob's program in the third:
  47 KB (8,394 words) - 02:12, 10 October 2012
• Binary search
  ...bisection strategy'', or ''binary search'', is a vast improvement over the linear search. ...ments of the array are simple scalar variables that take <math>O(1)</math> time to compare. However, because the array is sorted, we can do better than thi
  21 KB (3,719 words) - 05:17, 19 March 2017
• Binomial heap
  ...ath>m</math> and <math>n</math> can be merged in <math>O(\log(m+n))</math> time). ...wo tree, again of size <math>2^{k-1}</math>. This procedure takes constant time.
  15 KB (2,633 words) - 06:16, 10 October 2012
• Shunting yard algorithm
  ...o right. It also constructs the postfix notation from left to right. Every time an operand is encountered, it is immediately transferred to the output stre ...contribution to the running time.) The space requirement is also obviously linear.
  15 KB (2,569 words) - 19:07, 21 October 2015
• Maximum subvector sum
  ...'''61'''.</ref> In algorithmic programming competitions, Kadane's [[linear time]] algorithm for this problem is often useful as a building block within a m ...ef name="bentley"/> describes four algorithms for this problem, of running time <math>O(n^3)</math>, <math>O(n^2)</math>, <math>O(n\log n)</math>, and <mat
  9 KB (1,454 words) - 06:09, 3 May 2012