Linked Questions

4 votes
1 answer

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)...
edA-qa mort-ora-y's user avatar
0 votes
0 answers

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!
programmer's user avatar
197 votes
3 answers

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 ...
Raphael's user avatar
  • 72.7k
38 votes
3 answers

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 ...
wsaleem's user avatar
  • 581
7 votes
7 answers

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}$ ...
Tor Klingberg's user avatar
6 votes
3 answers

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 ...
forrestGump's user avatar
7 votes
2 answers

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 ...
Alex Smart's user avatar
8 votes
2 answers

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 ...
ithisa's user avatar
  • 357
6 votes
2 answers

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 ...
Petar Mihalj's user avatar
3 votes
2 answers

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$: ...
User123216454657's user avatar
4 votes
1 answer

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 ...
Michael's user avatar
  • 41
2 votes
4 answers

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) ...
Honinbo Shusaku's user avatar
6 votes
3 answers

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 ...
John Demetriou's user avatar
5 votes
3 answers

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 ...
jederik's user avatar
  • 267
6 votes
1 answer

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 ...
The111's user avatar
  • 161

15 30 50 per page