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.

Filter by
Sorted by
Tagged with
0
votes
1answer
11 views

solve time complexity of recurrence relation

We assume $n$ is a power of $2$. We normally say multiplication takes $\Theta(n^2)$ execution time. please show me process ...
0
votes
0answers
15 views

Expected runtime for hashing with a binary search tree as collision handling

I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
1
vote
0answers
15 views

Suggestions for a source of algorithm design problems?

I’m finishing up Roughgarden’s two-part algorithms course on edx, and it was good, but I didn’t actually ‘design and analyze’ many algorithms, the questions mostly tested whether you understood the ...
0
votes
1answer
22 views

Asymptotic runtime of recursive algorithm uisng subsitution method

I need to solve this question using the substitution method: $T(n) = 3T(n/2)+2n$ if $n>1$ otherwise, $T(n) = 1$ Note: $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$ $$a^{\log_b n} = n^{\log_b a}$$ ...
2
votes
2answers
43 views

Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set ...
3
votes
1answer
430 views

Why does the time hierarchy theorem use a rather intricate diagonal argument?

Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$? Where ...
0
votes
1answer
51 views

Knapsack Problem with Constraints on Item Values

Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight ...
0
votes
1answer
63 views

3Sum Why this O(nlogn) solution doesn't work?

I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \...
2
votes
1answer
51 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 ...
1
vote
1answer
34 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 ...
20
votes
2answers
752 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 ...
-3
votes
1answer
38 views
0
votes
0answers
25 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: ...
1
vote
1answer
57 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 ...
0
votes
1answer
38 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). <...
0
votes
1answer
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 ...
0
votes
1answer
43 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 ...
0
votes
1answer
30 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})$?
-5
votes
2answers
94 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 ...
2
votes
1answer
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 ...
3
votes
3answers
187 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 ...
1
vote
0answers
45 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 ...
2
votes
1answer
60 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 ...
1
vote
0answers
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 ...
1
vote
0answers
31 views

Intuition behind the entire (amortized) concept of Fibonacci Heap operations

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The potential function for the Fibonacci Heaps $H$ is defined as follows: $$\Phi(H)...
0
votes
0answers
22 views

Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling

I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
0
votes
1answer
33 views

Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
3
votes
1answer
65 views

$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al. In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$...
1
vote
0answers
18 views

Space complexity of using a pairwise independent hash family

I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011, https:...
0
votes
2answers
58 views

Analyzing space complexity of passing data to function by reference

I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^...
0
votes
0answers
32 views

Intersection of line segments induced by point sets from fixed geometry

I am reading up on algorithms and at the moment looking at the below problem from Jeff Erickson's book Algorithms. I solved (a) by seeing a relationship to the previous problem on computing the ...
1
vote
1answer
41 views

Tight upper bound for forming an $n$ element Red-Black Tree from scratch

I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order ...
2
votes
0answers
31 views

CLRS Exercise 6.4-5

The question is as follows: Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg n)$ https://walkccc.github.io/CLRS/Chap06/6.4/ This website provides a ...
2
votes
1answer
51 views

Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
2
votes
0answers
33 views

trouble solving the recurrence 4T(n/2) + n

I am having trouble figuring out how to solve this recurrence problem... $$ \begin{aligned} &4T(n/2) + n \\ = &4(4T(n/4) + n/4) + n \\ = &16T(n/4) + 2n \\ = &4^kT(n/2^k) + kn \end{...
0
votes
2answers
46 views

What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$

By unrolling the recursion, \begin{equation*} \begin{split} T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\ &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6 \\ &= (T(n^...
1
vote
1answer
24 views

For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that ...
1
vote
1answer
24 views

Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ ...
1
vote
1answer
12 views

Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?

I was going through the text Introduction to Algorithm by Cormen et. al. where I came across an excerpt which I felt required a bit of clarification. Now as far as I have learned that that while the ...
1
vote
0answers
37 views

Clarification of the analysis of the worst case situation of quicksort as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. and I came across their analysis of the worst case of the quicksort algorithm. I could not quite understand a few specific ...
2
votes
1answer
141 views

Average number of exchanges during first partition stage in Quicksort

I am trying to understand average no of exchanges in Quicksort. Here is the code to partition the array - ...
2
votes
1answer
40 views

Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure. The procedure is as follows: <...
2
votes
1answer
36 views

Clarification of the proof involving the regularity condition in Master Theorem

I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem. (The Statement of Master theorem) ...
2
votes
2answers
42 views

Algorithm to get the number of iterations needed, if possible, to get an specific 2 element array

I am fairly new to algorithms and I am dealing with a problem I cannot fully translate into mathematical language. So, I am given the array [1,1] and I can only perform one sum between their numbers ...
-1
votes
2answers
70 views

What would be the complexity for this relation?

The function: for (int i=1; i<n²; i++) for (int j=i; j<n; j++) print(j) Putting it into a relation, I got: $C1 + \sum_{i=1}^{n^2}(C2+...
0
votes
1answer
69 views

Clarification in the proof for the Bellamn-Ford algorithm

While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma: After k (k >= 0) iterations of relaxations, for any node u that has at least one path from s (the start ...
1
vote
2answers
47 views

Amortized time for dynamic array

I'm struggling to understand one part from the book "Cracking the coding interview". The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full ...
2
votes
1answer
28 views

Order notation subtractions in Fibonacci Heap

Can order notation on its own imply: $O(D(n)) + O(t(H)) - t(H) = O(D(n))$ My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0....
1
vote
0answers
13 views

Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's “Discrete Mathematics and its Application”

I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places ...

1
2 3 4 5
35