Questions tagged [complexity-theory]

33

votes

4

answers

Linear time v.s. Quadratic time

asked 2013-08-02T18:15:15.097

13

votes

1

answers

Big O of append in Golang

go append complexity-theory slice

asked 2013-06-26T23:40:35.953

8

votes

0

answers

Are there problems that can't be solved efficiently without arrays?

arrays haskell functional-programming complexity-theory theory

asked 2013-06-15T21:32:31.370

67

votes

4

answers

Example of a factorial time algorithm O( n! )

algorithm complexity-theory time-complexity factorial

asked 2013-05-15T02:49:06.777

8

votes

1

answers

What is the time complexity of INSERT, UPDATE and SELECT in SQLite?

sqlite time insert sql-update complexity-theory

asked 2013-04-09T08:01:29.523

8

votes

2

answers

How to find all nodes in a graph equidistant from a given set of nodes?

algorithm graph complexity-theory graph-algorithm

asked 2013-03-26T21:28:46.903

11

votes

3

answers

Big O for worst-case running time and Ω is for the best-case, but why is Ω used in worst case sometimes?

algorithm data-structures heap complexity-theory asymptotic-complexity

asked 2013-03-14T21:49:12.127

9

votes

3

answers

DoD Password Complexity: Users cannot reuse any of their previous X passwords

security encryption passwords complexity-theory stig

asked 2013-02-24T09:52:24.103

26

votes

9

answers

Find all the quadruples [a, b, c, d] where a^3 + b^3 = c^3 + d^3 when 1 <= a, b, c or d <= 10000

algorithm complexity-theory

asked 2013-01-22T08:13:37.930

8

votes

3

answers

Benefits of "both" arraylist and linkedlist... possible in java?

java data-structures arraylist linked-list complexity-theory

asked 2012-11-18T19:01:15.267

13

votes

1

answers

In-order traversal complexity in a binary search tree (using iterators)?

c++ algorithm complexity-theory

asked 2012-10-14T12:56:21.800

16

votes

7

answers

Random sequence iteration in O(1) memory?

c++ stl iterator complexity-theory permutation

asked 2012-09-17T13:41:55.317

8

votes

4

answers

Calculate the maximum distance between vectors in an array

algorithm complexity-theory

asked 2012-08-24T11:04:31.617

11

votes

3

answers

Time complexity for merging two sorted arrays of size n and m

sorting complexity-theory

asked 2012-06-14T18:31:19.327

15

votes

2

answers

How expensive is comparing two unordered sets for equality?

c++ set complexity-theory equality unordered-set

asked 2012-04-12T06:33:00.900

14

votes

4

answers

Combat strategy for ants

algorithm language-agnostic complexity-theory

asked 2011-12-20T11:00:09.030

12

votes

6

answers

Exactly how many comparisons does merge sort make?

algorithm sorting complexity-theory quicksort mergesort

asked 2011-12-16T14:25:23.960

14

votes

3

answers

size() complexity of STL containers in G++: which containers are O(n)?

c++ stl g++ complexity-theory

asked 2011-12-12T02:13:20.757

20

votes

3

answers

Intersection complexity

python set complexity-theory

asked 2011-11-12T04:07:15.897

18

votes

11

answers

Finding the closest fibonacci numbers

c++ algorithm math complexity-theory discrete-mathematics

asked 2011-10-20T22:31:44.987

11

votes

1

answers

Efficient Algorithms for Computing a matrix times its transpose

algorithm linear-algebra complexity-theory matrix-multiplication

asked 2011-09-28T03:12:05.880

43

votes

6

answers

What is the complexity of these Dictionary methods?

c# complexity-theory time-complexity

asked 2011-09-23T17:25:01.687

10

votes

5

answers

Optimal data structure for a special dictionary

algorithm data-structures hash complexity-theory trie

asked 2011-09-23T11:14:37.463

172

votes

8

answers

B-Tree vs Hash Table

mysql data-structures computer-science complexity-theory b-tree

asked 2011-09-05T09:43:17.933

63

votes

8

answers

why does accessing an element in an array take constant time?

c arrays time constants complexity-theory

asked 2011-09-04T07:31:51.133

22

votes

9

answers

Finding the first n largest elements in an array

c arrays algorithm complexity-theory

asked 2011-09-01T15:22:57.380

22

votes

2

answers

Finding out the duplicate element in an array

c arrays algorithm complexity-theory big-o

asked 2011-08-19T05:39:56.223

13

votes

3

answers

c++ practical computational complexity of <cmath> SQRT()

c++ complexity-theory sqrt cpu-cycles cpu-time

asked 2011-07-30T16:09:08.880

11

votes

4

answers

C++0x issue: Constant time insertion into std::set

c++ stl insert set complexity-theory

asked 2011-07-03T11:48:33.907

39

votes

6

answers

Are there any real O(n^n) algorithms?

algorithm complexity-theory big-o

asked 2011-05-27T18:22:23.580

12

votes

4

answers

Time complexity of accessing an element in a tuple

python complexity-theory tuples

asked 2011-05-27T14:03:41.183

10

votes

1

answers

How to measure complexity of a string?

.net algorithm string complexity-theory approximation

asked 2011-05-21T20:55:49.163

10

votes

5

answers

O(N*LogN) algorithm for the following problem

algorithm complexity-theory

asked 2011-05-06T13:38:24.727

9

votes

9

answers

Unit testing equals and hashcode - a complexity story

java unit-testing complexity-theory equals hashcode

asked 2011-04-23T13:18:38.263

19

votes

2

answers

how to determine if the kth largest element of the heap is greater than x

algorithm complexity-theory binary-heap

asked 2011-02-07T14:51:54.607

22

votes

4

answers

Example problems not in P nor in NP-complete but in NP

computer-science theory complexity-theory computation-theory

asked 2010-12-13T14:05:28.223

32

votes

8

answers

Missing number(s) Interview Question Redux

c++ math computer-science complexity-theory

asked 2010-12-10T05:54:40.940

119

votes

8

answers

Big-oh vs big-theta

algorithm complexity-theory

asked 2010-07-12T16:13:07.820

21

votes

8

answers

Does Big O Measure Memory Requirments Or Just Speed?

algorithm complexity-theory big-o

asked 2010-07-12T16:11:26.530

146

votes

5

answers

What guarantees are there on the run-time complexity (Big-O) of LINQ methods?

c# .net linq algorithm complexity-theory

asked 2010-05-09T22:29:05.690

113

votes

3

answers

What is O(log* N)?

algorithm math complexity-theory logarithm iterated-logarithm

asked 2010-03-05T15:06:05.857

1483

votes

13

answers

What are the differences between NP, NP-Complete and NP-Hard?

computer-science complexity-theory np np-complete np-hard

asked 2009-12-07T01:11:36.183

82

votes

5

answers

What is the meaning of O( polylog(n) )? In particular, how is polylog(n) defined?

algorithm full-text-search compression complexity-theory

asked 2009-11-26T01:45:59.653

20

votes

3

answers

Why is the complexity of A* exponential in memory?

algorithm artificial-intelligence graph complexity-theory a-star

asked 2009-11-11T14:12:06.993

10

votes

1

answers

Are there any online algorithms for planarity testing?

algorithm complexity-theory graph-theory

asked 2009-10-22T04:19:37.127

126

votes

7

answers

Is Big O(logn) log base e?

math binary-tree complexity-theory big-o

asked 2009-10-15T00:28:53.797

189

votes

34

answers

How to find the lowest common ancestor of two nodes in any binary tree?

algorithm binary-tree complexity-theory least-common-ancestor

asked 2009-09-27T21:01:41.943

43

votes

5

answers

What is the runtime complexity of python list functions?

python complexity-theory

asked 2009-06-17T07:28:54.537

89

votes

7

answers

O(N log N) Complexity - Similar to linear?

language-agnostic complexity-theory quicksort

asked 2009-06-07T18:59:16.417

29

votes

8

answers

Sorting in linear time?

algorithm sorting complexity-theory time-complexity

asked 2009-04-14T22:25:08.070

Questions tagged complexity-theory