Linked Questions
39 questions linked to/from How can we assume that basic operations on numbers take constant time?
4
votes
1
answer
256
views
Complexity calculations, assumptions on basic costs [duplicate]
Possible Duplicate:
How can we assume comparison, addition, … between numbers is $O(1)$
When we calculate the time-complexity of some algorithm we make many simplifications (or assumptions)...
- 1,538
0
votes
0
answers
24
views
running time of bitwise operations [duplicate]
Assuming we have two integers a and b, if we do bitwise operations like a & b or a | b, is the running time O(1) (constant) or is it O(b) where b is the number of bits in a and b?
Thanks!
- 159
194
votes
3
answers
26k
views
Is there a system behind the magic of algorithm analysis?
There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
- 72k
38
votes
3
answers
5k
views
How is algorithm complexity modeled for functional languages?
Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case ...
- 581
7
votes
7
answers
6k
views
Is there a meaningful difference between O(1) and O(log n)?
A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
- 171
6
votes
3
answers
9k
views
Quicksort vs. insertion sort on linked list: performance
I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm.
Does anyone have any idea why this is?
Insertion sort has a ...
- 787
7
votes
2
answers
859
views
How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?
A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set ...
- 165
8
votes
2
answers
4k
views
How are hash tables O(1) taking into account hashing speed?
Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity.
However, this assumes the lengths of the elements are constant. Computing the hash of an ...
- 357
6
votes
2
answers
3k
views
Is it possible to get Nth Fibonacci number in sublinear time?
I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I've decided to check out if you agree with my ...
- 148
3
votes
2
answers
11k
views
Time complexity of recursive power code
While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$:
...
4
votes
1
answer
3k
views
Time complexity of arithmetic operations
I want to calculate the time complexity of the listed algorithms, please correct if I'm doing something wrong:
The question is, do some operations like multiplying, dividing, or plus really affect on ...
- 41
2
votes
4
answers
3k
views
How does size of a number in an array affect time complexity algorithm analysis?
This question stems from this question and this answer. I also want to preface this question by stating that this question is done from the perspective of a RAM (or PRAM if it's more accurate term) ...
- 531
6
votes
3
answers
609
views
Shouldn't complexity theory consider the time taken for different operations?
I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison.
I am trying to understand why each basic operation ...
- 413
6
votes
1
answer
697
views
Can we read N numbers in O(N) time?
In a different post it came up that
(using the Turing machine model of computation),
it is not even safe to say that $N$ numbers can be read in $O(N)$ time.
To me this is boggling since
it's ...
- 161
5
votes
3
answers
540
views
Why are hash map look-ups assumed to be $O(1)$ on average
To look up a key in a hash map you have to
calculate its hash
find the entry in the resulting hash bucket
Hash calculation takes at least $O(l)$ operations when the hashes are $l$-bit-numbers.
When ...
- 267