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
45 views

What could be the most efficient algorithm to find index in an array that matches given conditions?

I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A[j-1]>=A[j]<=A[j+1]. Example: ...
0
votes
1answer
34 views

Inversions of Insertion Sort and Bubble Sort

An array with bubblesort time $\Theta(n)$ is nothing but a sorted array like: A = 1 2 3 4 5 No swaps are done so only $n - 1$ comparisons. An array with insertionsort run time $\Theta(n^2)$ is a ...
0
votes
2answers
42 views

inversions in array

If the worst case arrays {5 4 3 2 1} have number of inversions as Θ(n^2) => n(n-1)/2 swaps The best case arrays {1 2 3 4 5} have number of inversions 0(no swap) What kind of arrays have number of ...
0
votes
1answer
22 views

sort is equal to inversions logic

In Bubble sort, the number of swaps/comparisons is equal to the number of inversions. 1st pass it will do (n -1) comparison 2nd pass it will do (n-2) comparison....so on (n-1)n = n^2 - n Worst case ...
0
votes
1answer
15 views

simplified into asymptotic notation

I have a function that needs to be represented in theta form. The below is my answer. But the correct answer is 𝜃(n.2^n) Can someone please explain me how??
0
votes
0answers
18 views

Amortized Analysis of extract-min-operation of Fibonacci Heap

I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is: The potential before ...
10
votes
2answers
4k views

Can I multiply Big-O time complexities?

Can I multiply Big-O time complexities? For example: $O(n) \cdot O(n) = O(n^2)$? UPDATE: The question came from my observation that different sources analyze their algorithms in different ways. For ...
0
votes
0answers
40 views

Analyzing Hybrid Merge and Insertion Sort

We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case. The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small ...
-1
votes
0answers
48 views

What is the best data structure for this set?

This is an actual application problem that I thought maybe looking at it in an abstract sense will give the best solution. 1- We have a dataset of size N in the range of 2¹⁶-2¹⁷ item 2-Insertions &...
1
vote
1answer
59 views

Prove that the following algorithm for division and remainders of natural numbers is correct

I am currently brand new to the correctness proof method, and have stumbled upon this algorithm which I find very tricky. Prove that the following algorithm for division and remainders of natural ...
1
vote
1answer
21 views

Complexity of checking graph separation

Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
0
votes
0answers
143 views

Some Confusions in Ricart Agrawala second algorithm-token based algorithm for mutual exclusion

Resources that I followed to learn-: http://www.ejbtutorial.com/lectures/petru/lect6-7.frm.pdf https://cis.temple.edu/~wu/teaching/Spring2020_CIS5644_Distributed_Computing/distributed-computing-2020-...
0
votes
0answers
15 views

Is ordering achieved by central server algorithm?

ME3 specifies that the first process be granted access before the second Ordering-: Requests are granted in the order they were requested. Colouris Distributed Systems book-: The reader should ...
0
votes
1answer
29 views

Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
0
votes
1answer
27 views

Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
1
vote
2answers
49 views

Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?

I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...
0
votes
0answers
14 views

Precondition of all-pairs shortest-paths algorithm

In Retiming Synchronous Circuitry , why put a negative sign to d(u) in step 1 ? Why there is no subtraction operation for W(u, v) in step 3?
0
votes
2answers
61 views

How do you justify making algorithm subroutines more efficient when Big-O notation only includes the dominant term?

I don't really understand time complexity, and wanted some clarification in this hypothetical situation. If I were being given items one by one, and I wanted a list of them all in the reverse order I ...
3
votes
0answers
30 views

Running time analysis of Savitch's algorithm

Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC. Is ...
0
votes
1answer
43 views

Need help understanding tightest lower bound ( BigOmega ) of n!

I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(...
0
votes
1answer
43 views

Ask for help to prove a inequality, thanks

Can anyone help to prove that $\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) > cn$ for some constant $c>0$? Here $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer ...
0
votes
0answers
9 views

Analysis of straggler in tree-based parallel execution

Does anyone have a reference on how tree-based parallel execution can reduce the chance of getting a straggler. Google Dremel and Jeff Dean's talk at slide 53 both talk about using tree-based parallel ...
-1
votes
1answer
52 views

Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
2
votes
1answer
37 views

Counting primitive operations on recursive functions

I'm reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given ...
2
votes
1answer
46 views

Understanding the upper bound proof for quick sort

I'm trying to understand the average run time of quicksort which is $O(n \log n)$. I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
0
votes
1answer
35 views

Understanding a summation notation. Sum(j=2 to n) j - 1

I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs. I know how ...
1
vote
1answer
38 views

Proof of approximation ratio for approximate triangle inequality version of k-center

Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
1
vote
1answer
76 views

Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?

I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me): Vector-representation based models. One naive approach would be to represent G by flattening ...
1
vote
1answer
86 views

How to prove the my greedy algorithm for placing guards?

Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images ...
0
votes
1answer
40 views

an algorithm to find the shortest path between two vertices whose weight is divided by 3?

I am trying to think of an algorithm such that giving a graph $G(V,E)$, and a weight function $w\colon E \to \mathbb{N}_+$ (which means giving every edge in the graph a positive weight), and a source ...
0
votes
3answers
47 views

Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?

I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to ...
0
votes
1answer
85 views

How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

Can somebody help me with this recurrence please? $T(n)=4T(\sqrt{n}/3)+(\log n)^2$
0
votes
3answers
80 views

$(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
4
votes
1answer
149 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
2
votes
2answers
36 views

Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, ...
0
votes
0answers
24 views

Recursive approach of longest common subsequence

I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong. I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
-1
votes
1answer
156 views

Proof of Correctness : Arranging the sheep

I've come across a question in Codeforces contest 719(Div - 3). The problem goes like this : I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
-1
votes
1answer
114 views

recursive algorithm to sort children and parents based on value

Edit: I dont have CS background and I'm still studying Algorithms, so any help will count! I met this algorithm while I was in interview, I didn't know what category it falls in, and hence I was ...
2
votes
2answers
134 views

Sorting by repeated reversal

Let $A$ be an array of $n$ integers containing the numbers $\{1, 2, \dots , n\}$ in some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i < j ≤ n$, let $\mathrm{Reverse}(A, i, j)$ be a ...
-1
votes
1answer
21 views

How would the classes of regular, context-free, decidable, and Turing-recognizable languages relate to each other

I'm a bit confused as to how they relate to each other. I think I understand them individually but not sure how they would relate.
-1
votes
2answers
78 views

sum of array with O(1)

I have an array of n elements. Smallest element that exists in the array is x and the largest element is x+n. None of the numbers between x to x + n is missing from the array. i need an algorithm to ...
0
votes
2answers
115 views

How to show working for summing of Big O notation

The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed? $$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$
-1
votes
2answers
31 views

Undecidable or Decidable

In a typical data structures class, we look at a variety of problems: finding an element in a list, sorting a list, balancing a binary search tree, finding the shortest paths in a graph, etc. Would ...
0
votes
1answer
21 views

What is the difference between designing an algorithm that solves a problem and creating a TM that decides a language?

Question: What is the difference between designing an algorithm that solves a problem and creating a Turing machine that decides a language? A turing machine "decides" the language if it &...
0
votes
1answer
40 views

Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?

In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words: Multiplications are everything. The exponent on the eventual running time is fully dependent only ...
0
votes
0answers
116 views

Average number of comparisons for a successful search of a prime number in a binary search tree

A binary search tree is constructed by inserting the following value sequentially: $$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$ Let $p_v$ be the probability to search for the value $v$ in the binary search tree (...
2
votes
2answers
79 views

Big-O notation for lower bound instead of Big-Omega

In the Wikipedia's Binary search tree, one can read Traversal requires $O(n)$ time, since it must visit every node. Since it is question of a lower bound, shouldn't we write Traversal requires $\...
1
vote
1answer
40 views

Do the following two CFGs describe the same language

Do the following two CFGs describe the same language S → aS | bS | ε S → aS | Sb | ε Would the answer to this be no, because the order can't be switched? bS and Sb are different. I'm a bit confused ...
0
votes
0answers
28 views

How to know that the substrings 01 and 10 does not require an infinite amount of memory to count the substrings [duplicate]

Why does {w | w has equal number of 01 and 10 substrings} not require an infinite amount of memory to “count” the number of 01 and 10 substrings?
0
votes
0answers
40 views

Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem. ...

1
2 3 4 5
37