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
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$? ? ...
3
votes
2answers
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 $...
0
votes
1answer
29 views

Exact runtime of median of median algorithm

Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be $$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$ which can be proven by induction equal to $...
0
votes
2answers
85 views

Is the halting problem pointless?

Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot ...
0
votes
0answers
27 views

Algorithm for specific load balancing/arbitration problem

I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
0
votes
1answer
19 views

Prove that if g ( n ) ∈ ω ( 1 ) and f ( n ) ∈ o ( g ( n ) ) , t h e n 2 f ( n ) ∈ o ( 2 g ( n ) )?

I was going over this question in my Algorithms class and could'nt understand why first condition has to be met? How would g ( n ) ∈ ω ( 1 ) affect our reasoning. ...
1
vote
0answers
59 views

Proving a tighter upperbound (big-O) for this problem

Motivation So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: ...
-1
votes
0answers
16 views

Checking if the spacetime complexity is the same for top-down and bottom up approach but different for runtime

Seeking help for the below bullet points. I will like to check whether the space-time complexity for both solutions is the same. Also, the run-time complexity for both is different. Here is the ...
0
votes
0answers
29 views

The following time complexity is right for the given algorirthm

Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct? ...
1
vote
1answer
27 views

Finding the area of a rectangle in python [closed]

Q: Standard input consists of exactly four integers, first x1 and y1, the coordinates of the bottom-left corner of a rectangle, then x2 and y2, the coordinates of the top-right corner. Write a Python ...
0
votes
0answers
16 views

What should I consider to analyze my proposed ILP in a scientific environment?

I am working on an NP-complete problem and, I have proposed an efficient (as I think) Integer Linear programming to find the solutions in some small instances. My algorithm can work on a greater size ...
0
votes
0answers
131 views

divide a sorted array into k subarrays with their intervals are same and count integers in the interval without accessing the data

Given a positive integer k and an array A[1..n] that contains n positive integers in ascending order, count the number of integers that its value lie in $(\frac{100(i−1)}{k}, \frac{100i}{k}]$ for ...
1
vote
1answer
22 views

Determing Big Oh Of Given Data

I'm trying to determine the big O time complexity of the following data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should ...
0
votes
0answers
44 views

Create a potential function for an abstract queue data structure to show constant amortized-time complexity

Consider a variation of a Queue called MaxQueue, Q, that has the following operations: dequeue(Q): removes and returns the first element of Q enqueue(Q, s): Appends the integer s to the end of Q ...
0
votes
0answers
20 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 ...
2
votes
0answers
23 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
25 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
49 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
442 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
56 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
68 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
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 ...
1
vote
1answer
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 ...
20
votes
2answers
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 ...
-3
votes
1answer
40 views
0
votes
0answers
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: ...
1
vote
1answer
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 ...
0
votes
1answer
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). <...
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
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 ...
0
votes
1answer
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})$?
-5
votes
2answers
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 ...
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
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
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
37 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
34 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
66 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
21 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
71 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
33 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
46 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
33 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
56 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
36 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
2 3 4 5
35