721 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
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
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
1 vote
2k views

### Time Complexity of ${n \choose k}$

I want to know the time complexity of specifically calculating ${n \choose k}$ where it is defined as $${n \choose k} = \frac{n!}{k!(n-k)!}.$$ If the factorial function is recursive $O(n)$: ...
• 161
1 vote
403 views

• 2,911
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