262 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
25 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
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 ...
• 72.7k
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
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}$ ...
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
883 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 ...
• 175
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
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
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$: ...
4k 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
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) ...
635 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 ...
652 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
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 ...