Questions tagged [complexity-theory]
Computational Complexity Theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty. Particularly common in programming is *amortized analysis* for time or space. Questions must relate to programming. For theoretical Computer Science questions, please ask on https://cs.stackexchange.com/.
complexity-theory
4,652
questions
5373
votes
43
answers
831k
views
What is a plain English explanation of "Big O" notation?
I'd prefer as little formal definition as possible and simple mathematics.
- 61.8k
1442
votes
12
answers
709k
views
What are the differences between NP, NP-Complete and NP-Hard?
What are the differences between NP, NP-Complete and NP-Hard?
I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what's ...
- 54.1k
1039
votes
10
answers
879k
views
How can I find the time complexity of an algorithm?
I have gone through Google and Stack Overflow search, but nowhere I was able to find a clear and straightforward explanation for how to calculate time complexity.
What do I know already?
Say for code ...
- 47.4k
978
votes
24
answers
536k
views
Big O, how do you calculate/approximate it?
Most people with a degree in CS will certainly know what Big O stands for.
It helps us to measure how well an algorithm scales.
But I'm curious, how do you calculate or approximate the complexity of ...
- 18.3k
877
votes
19
answers
497k
views
How can building a heap be O(n) time complexity?
Can someone help explain how can building a heap be O(n) complexity?
Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the ...
- 17.8k
526
votes
8
answers
130k
views
What is Constant Amortized Time?
What is meant by "Constant Amortized Time" when talking about time complexity of an algorithm?
- 6,207
441
votes
5
answers
375k
views
Difference between Big-O and Little-O Notation
What is the difference between Big-O notation O(n) and Little-O notation o(n)?
- 7,271
417
votes
7
answers
464k
views
Determining complexity for recursive functions (Big O notation)
I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve these ...
- 4,849
395
votes
12
answers
422k
views
Computational complexity of Fibonacci Sequence
I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci ...
- 81k
365
votes
33
answers
81k
views
Are there any O(1/n) algorithms?
Are there any O(1/n) algorithms?
Or anything else which is less than O(1)?
275
votes
10
answers
311k
views
Is log(n!) = Θ(n·log(n))?
I am to show that log(n!) = Θ(n·log(n)).
A hint was given that I should show the upper bound with nn and show the lower bound with (n/2)(n/2). This does not seem all that intuitive to me. Why would ...
- 6,203
272
votes
6
answers
175k
views
What's "P=NP?", and why is it such a famous question? [closed]
The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting?
Oh, and for extra credit, please post a proof of the statement's ...
- 21.6k
190
votes
34
answers
189k
views
How to find the lowest common ancestor of two nodes in any binary tree?
The Binary Tree here is may not necessarily be a Binary Search Tree.
The structure could be taken as -
struct node {
int data;
struct node *left;
struct node *right;
};
The maximum ...
- 2,535
189
votes
8
answers
250k
views
HashMap get/put complexity
We are used to saying that HashMap get/put operations are O(1). However it depends on the hash implementation. The default object hash is actually the internal address in the JVM heap. Are we sure it ...
- 41.6k
186
votes
6
answers
41k
views
Are 2^n and n*2^n in the same time complexity?
Resources I've found on time complexity are unclear about when it is okay to ignore terms in a time complexity equation, specifically with non-polynomial examples.
It's clear to me that given ...
- 2,643
166
votes
8
answers
111k
views
B-Tree vs Hash Table
In MySQL, an index type is a b-tree, and access an element in a b-tree is in logarithmic amortized time O(log(n)).
On the other hand, accessing an element in a hash table is in O(1).
Why is a hash ...
- 15.6k
161
votes
3
answers
233k
views
Time complexity of python set operations?
What is the the time complexity of each of python's set operations in Big O notation?
I am using Python's set type for an operation on a large number of items. I want to know how each operation's ...
- 10.8k
151
votes
8
answers
16k
views
Throwing cats out of windows
Imagine you're in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can ...
- 6,932
144
votes
5
answers
42k
views
What guarantees are there on the run-time complexity (Big-O) of LINQ methods?
I've recently started using LINQ quite a bit, and I haven't really seen any mention of run-time complexity for any of the LINQ methods. Obviously, there are many factors at play here, so let's ...
- 47.4k
123
votes
3
answers
127k
views
What would cause an algorithm to have O(log log n) complexity?
This earlier question addresses some of the factors that might cause an algorithm to have O(log n) complexity.
What would cause an algorithm to have time complexity O(log log n)?
- 367k
119
votes
7
answers
64k
views
Is Big O(logn) log base e?
For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural ...
- 2,158
118
votes
8
answers
153k
views
Big-oh vs big-theta [duplicate]
Possible Duplicate:
What is the difference between Θ(n) and O(n)?
It seems to me like when people talk about algorithm complexity informally, they talk about big-oh. But in formal situations, I often ...
- 2,351
118
votes
6
answers
50k
views
Why is the knapsack problem pseudo-polynomial?
I know that Knapsack is NP-complete while it can be solved by DP. They say that the DP solution is pseudo-polynomial, since it is exponential in the "length of input" (i.e. the numbers of bits ...
- 41.6k
111
votes
13
answers
167k
views
What's the fastest algorithm for sorting a linked list?
I'm curious if O(n log n) is the best a linked list can do.
- 6,804
109
votes
3
answers
54k
views
108
votes
6
answers
157k
views
.NET console application exit event
In .NET, is there a method, such as an event, for detecting when a console application is exiting? I need to clean up some threads and COM objects.
I am running a message loop, without a form, from ...
- 2,661
95
votes
7
answers
61k
views
How to understand the knapsack problem is NP-complete?
We know that the knapsack problem can be solved in O(nW) complexity by dynamic programming. But we say this is a NP-complete problem. I feel it is hard to understand here.
(n is the number of items. ...
- 1,295
93
votes
16
answers
107k
views
Example of O(n!)?
What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.
- 1,179
90
votes
7
answers
146k
views
Difference between O(n) and O(log(n)) - which is better and what exactly is O(log(n))?
This is my first course in data structures and every lecture / TA lecture , we talk about O(log(n)) . This is probably a dumb question but I'd appreciate if someone can explain to me exactly what does ...
- 21.6k
87
votes
7
answers
113k
views
O(N log N) Complexity - Similar to linear?
So I think I'm going to get buried for asking such a trivial question but I'm a little confused about something.
I have implemented quicksort in Java and C and I was doing some basic comparissons. ...
- 29.1k
87
votes
4
answers
57k
views
What is the complexity of regular expression?
What is the complexity with respect to the string length that takes to perform a regular expression comparison on a string?
- 14.6k
84
votes
4
answers
89k
views
Python dictionary keys. "In" complexity
Quick question to mainly satisfy my curiosity on the topic.
I am writing some large python programs with an SQlite database backend and will be dealing with a large number of records in the future, ...
- 4,416
83
votes
9
answers
50k
views
Time complexity of unshift() vs. push() in Javascript
I know what is the difference between unshift() and push() methods in JavaScript, but I'm wondering what is the difference in time complexity?
I suppose for push() method is O(1) because you're just ...
- 1,899
81
votes
2
answers
77k
views
multiset, map and hash map complexity
I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:
inserting entries
accessing entries
retrieving entries
comparing entries
Harry
77
votes
5
answers
41k
views
es6 Map and Set complexity, v8 implementation
Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)?
(I know that the standard doesn't guarantee that)
- 26.3k
76
votes
6
answers
214k
views
Time complexity of accessing a Python dict
I am writing a simple Python program.
My program seems to suffer from linear access to dictionaries,
its run-time grows exponentially even though the algorithm is quadratic.
I use a dictionary to ...
- 3,840
74
votes
5
answers
31k
views
What is the meaning of O( polylog(n) )? In particular, how is polylog(n) defined?
Brief:
When academic (computer science) papers say "O(polylog(n))", what do they mean? I'm not confused by the "Big-Oh" notation, which I'm very familiar with, but rather by the ...
- 8,909
74
votes
9
answers
21k
views
General rules for simplifying SQL statements
I'm looking for some "inference rules" (similar to set operation rules or logic rules) which I can use to reduce a SQL query in complexity or size.
Does there exist something like that? Any papers, ...
- 26.5k
74
votes
2
answers
7k
views
Why SortedSet<T>.GetViewBetween isn't O(log N)?
In .NET 4.0+, a class SortedSet<T> has a method called GetViewBetween(l, r), which returns an interface view on a tree part containing all the values between the two specified. Given that ...
- 2,821
73
votes
3
answers
69k
views
What's the Time Complexity of Average Regex algorithms?
I'm not new to using regular expressions, and I understand the basic theory they're based on--finite state machines.
I'm not so good at algorithmic analysis though and don't understand how a regex ...
- 6,246
69
votes
8
answers
156k
views
Which is better: O(n log n) or O(n^2)
Okay so I have this project I have to do, but I just don't understand it. The thing is, I have 2 algorithms. O(n^2) and O(n*log2n).
Anyway, I find out in the project info that if n<100, then O(n^2) ...
- 693
68
votes
7
answers
60k
views
Intuitive explanation for why QuickSort is n log n?
Is anybody able to give a 'plain english' intuitive, yet formal, explanation of what makes QuickSort n log n? From my understanding it has to make a pass over n items, and it does this log n times......
- 4,142
68
votes
8
answers
28k
views
Is list::size() really O(n)?
Recently, I noticed some people mentioning that std::list::size() has a linear complexity.
According to some sources, this is in fact implementation dependent as the standard doesn't say what the ...
- 5,619
68
votes
3
answers
77k
views
What is O(1) space complexity?
I am having a hard time understanding what is O(1) space complexity. I understand that it means that the space required by the algorithm does not grow with the input or the size of the data on which ...
- 879
67
votes
7
answers
19k
views
Explain the proof by Vinay Deolalikar that P != NP [closed]
Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP.
Could someone explain how this proof works for us less mathematically ...
66
votes
10
answers
217k
views
Time complexity of nested for-loop
I need to calculate the time complexity of the following code:
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
// Some code
}
}
Is it O(n^2)?
- 912
66
votes
4
answers
76k
views
Example of a factorial time algorithm O( n! )
I'm studying time complexity in school and our main focus seems to be on polynomial time O(n^c) algorithms and quasi-linear time O(nlog(n)) algorithms with the occasional exponential time O(c^n) ...
- 5,448
63
votes
2
answers
7k
views
Is it a good idea to store data as keys in HashMap with empty/null values?
I had originally written an ArrayList and stored unique values (usernames, i.e. Strings) in it. I later needed to use the ArrayList to search if a user existed in it. That's O(n) for the search.
My ...
- 861
63
votes
8
answers
7k
views
Sorting algorithms for data of known statistical distribution?
It just occurred to me, if you know something about the distribution (in the statistical sense) of the data to sort, the performance of a sorting algorithm might benefit if you take that information ...
- 54.6k
62
votes
6
answers
16k
views
Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?
Assume I have two algorithms:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//do something in constant time
}
}
This is naturally O(n^2). Suppose I also have:
for (int i ...
- 7,178