# Questions tagged [algorithm-analysis]

Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.

1,713 questions
Filter by
Sorted by
Tagged with
28 views

### How can I prove the correctness of this exponentiation algorithm using induction?

I have the following algorithm. How could I prove it using induction that for every $n> = 0$, $exp (n) = 2 ^ n$? ? ...
90 views

### Upper bounds for a binomial coefficient

I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k$...
29 views

52 views

### Course teaching time complexities in real life systems

Having mis-read What course in CS deals with the study of RAM, CPU, Storage? I now wonder what course in CS deals with time and space complexities including GPUs, CPU caches in multiple levels, seek ...
37 views

### Complexity of algorithm partitioning input into parts of size $n/100$ and $99n/100$

Merge sort always divides array of size $n$ into parts each of size $n/2$. It then merges these two parts. So its recurrence relation is $T(n)=2T(n/2) + O(n)$. What if there is an algorithm which is ...
781 views

### What is the intuition behind Strassen's Algorithm?

I came across Strassen's algorithm for matrix multiplication, which has time complexity $O(n^{2.81})$, significantly better than the naive $O(n^3)$. Of course, there have been several other ...
40 views

### Finding the worst case running time of this piece of code?

I am working with this code: ...
27 views

### How to Reconcile Apparent Discrepancy in this Algorithm's Runtime?

I'm currently working through Algorithms by Dr. Jeff Erickson. The following is an algorithm presented in the book: ...
69 views

### How to prove ln(n) = Θ(log2 n)?

This is a homework problem and I'm not sure how to do it correctly. It says "Prove ln(n) = Θ(log2 n) with n = odd number". Bu using Natural logarithm rules, we can somehow know this is ...
41 views

### How to calcualte the Big-O complexity of the following algorithm?

I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3). <...
46 views

### Scoring the postal code mismatch

I have two postal code (fixed size of 6 digits) to compare and return the mismatch score. where the mismatch weight of initial indexes are higher, then keep reducing. Example postal code 123456, with ...
48 views

### What is the difference between Big O, Omega, and Theta?

I know that this question is asked a lot of time but I don't understand or I think, I got lost when I was reading Introduction to algorithms They said, "It is not contradictory, however, to say ...
37 views

### what would be the time complexity of DBSCAN algorithm?

what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?
104 views

### solving recurrence T(n) = T(√n) + theta((lg lg n))

My solution: let m = lg n. Then n = 2^m. T(2^m) = T(2^(m/2)) + theta(lgm). Let S(m) = T(2^m). Then S(m) = S(m/2) + theta(lgm). Applying master theorem, I get m^(lg1) = 1 which is asymptotically ...
42 views

### Error in pivot selection algorithm for merge phase [Sorting]

In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart ...
189 views

### Book recommendations on the analysis of randomized algorithms

I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to ...
46 views

### Algorithm suggestion to order data with specific condition

Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller hamming distance should be placed as ...
61 views

### Difficulty in few steps in proof of “Amortized cost of $\text{Find-Set}$ operation is $\Theta(\alpha(n))$”assuming union by rank, path compression

I was reading the section of data structures for disjoint sets from the text Introduction to Algorithms by Cormen et. al .I faced difficulty in understanding few steps in the proof of the lemma as ...
39 views

### Counting one's in a stream of bits

I have to count the number of one's in last $m$ bits in a stream of bits and $m \leq n,$ where $n$ is the window size and it should take polylogarithmic space in $n$. I could only store last $n$ bits ...