Linked Questions

3
votes
1answer
160 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)...
0
votes
0answers
20 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!
163
votes
3answers
18k 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 ...
38
votes
3answers
4k 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 ...
5
votes
7answers
2k 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}$ ...
6
votes
3answers
8k 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 ...
6
votes
2answers
620 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 ...
6
votes
2answers
2k 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 ...
8
votes
2answers
2k 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 ...
2
votes
2answers
5k 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$: ...
6
votes
3answers
339 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 ...
2
votes
4answers
1k 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) ...
4
votes
1answer
430 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 ...
14
votes
2answers
431 views

Time-space tradeoff for missing element problem

Here is a well-known problem. Given an array $A[1\dots n]$ of positive integers, output the smallest positive integer not in the array. The problem can be solved in $O(n)$ space and time: read the ...
4
votes
3answers
186 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 ...

15 30 50 per page