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
1
vote
2answers
33 views

Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R". ...
1
vote
1answer
20 views

Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current ...
1
vote
1answer
29 views

Why postfix is used more often than prefix expression?

i was reading stack and i came across the infix, preifx and postfix expression.So i understood that why postfix /prefix expressions are preferred over infix expression ( due to its unambiguous nature) ...
1
vote
0answers
16 views

How to find the asymptotic bit cost

I know from a general point of view what big O notation is. I have taken an algorithms class before that was all implementations and did well. I am now in an algorithms class that is mostly theory and ...
-1
votes
0answers
24 views

Faster Algorithm v/s Faster Machine [closed]

(a) Suppose that a particular algorithm has time complexity T(n)=5nlog(n), and executing an implementation of it on a particular machine takes T seconds for n inputs. Now suppose that we are presented ...
2
votes
0answers
32 views

How does the maximum number of guesses needed to win Mastermind (board game) change as the size of the board increases?

Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm: Create a set S of remaining possibilities (...
4
votes
2answers
905 views

Generating random words by grammar

A bit of context I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
1
vote
1answer
43 views

Space complexity of Travelling Salesman Problem

I am having trouble coming up with the space complexity of the TSP algorithm. https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ To me the space complexity for the brute force is the ...
1
vote
1answer
31 views

Proving the optimality of an algorithm

I proposed an algorithm and I want to prove its optimality. It is not a greedy algorithm. I have the whole searching space $\mathcal{S}$ and I only search inside a subset of this searching space $\...
3
votes
1answer
243 views

Construct a DAG from given multiple topological orderings

I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as ...
1
vote
1answer
49 views

converting for loop into mathematical notation

I am a bit confused with a problem that I am having.I am trying to do an amoritized analysis and I am able to represent the function that I want to use using code. I coded the function as follows: <...
0
votes
1answer
19 views

Need help analyzing the runtime analysis of this algorithm/algorithms in general

This is the algorithm I was trying to find the runtime of (doSomething) - ...
0
votes
1answer
41 views

$ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity

My algorithms and data structures' book states that to create a dynamic array the following procedure is followed: Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in ...
2
votes
1answer
18 views

Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix

Ryser has shown that the permanent of an $n \times n$ matrix $A=(a_{ij})$ can be expressed as \begin{align} Perm(A) = (-1)^n \sum_{s \subset [n]} (-1)^{|s|} \prod_{i=1}^n \sum_{j \in s} a_{ij}, \end{...
-1
votes
1answer
68 views

Asymptotic Analysis of Nested Loops with Conditionals

I'm trying to run an analysis of a set of nested loops so that I can determine the value of variable sum after the outer loop is finished. The code is as follows: <...
1
vote
0answers
25 views

Time Complexity of a Naive Solution to Merge K Sorted Arrays

There is a leetcode question about merging k sorted arrays. I would like to be able to explain the time complexity of the following naive solution: ...
-2
votes
0answers
16 views

Find a letter in a sequence using algorithms

Let us consider the following searching problem Input: A sequence of n numbers A:[a1, a2, .... an] and a value $v$. Output: An index i such that $v$=A[i] or the special value NIL if v does not. ...
0
votes
2answers
46 views

Algorithm Running Time

I'll do my best to explain my question but what I'm wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such: If a $\Theta(\log_2{n})...
1
vote
1answer
37 views

Determining asymptotic notation of a complex function

$$ 5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40 $$ I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
1
vote
1answer
44 views

Where to find practical exercises for algorithm analysis?

What is a good book or resource to find practical exercises of analysis of the complexity of concrete algorithm implementations (that is, which asymptotic complexity does a particular code have)? I'...
0
votes
2answers
83 views

“Subpaths” of Dijkstra's shortest path also shortest?

I have trouble putting this into formal mathematical terms, so let's suppose that I found the shortest path from A to E as A > C > D > B > F > E with Dijkstra's algorithm. Am I correct in assuming ...
-1
votes
0answers
22 views

(Quiz/Algorithm) How many boxes are needed?

I have X pieces to store in Y boxes. The boxes vary in size and contain N, M, L, Q pieces. How do I find which boxes and how many boxes to use, in order to use as few of them as possible and without ...
-1
votes
0answers
48 views

Time Complexity of an recursive Algorithm

Goodmorning, I have to analyze the time complexity of this algorithm: Pseudocode: ...
0
votes
1answer
33 views

What is the algorithmic complexity of this?

I'm practicing leet code questions and want to understand more fully how to determine Big O notation. What is the algorithmic complexity of my solution to the following problem? O(n^2) ? For every ...
0
votes
2answers
41 views

Time complexity for concatenating strings

I was going through this piece of code from an algorithms books and something doesn't look clear Please ignore the spelling errors, How does 0(x + 2x + nx) reduce to o(xn^2) ? My analogy, assuming ...
0
votes
3answers
43 views

Primality testing algorithm

Say, I would like to check a hypothesis concerning primes. Something like "there exists a prime between $n$ and $2n$ for every choice of $n$". I would like to run a code in MATLAB for choices of $n$ ...
1
vote
1answer
33 views

Lower bound for Merge Sort running time

I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log_2 n)$. Here's my attempt: Suppose there is some $c>0$ and a positive integer $...
0
votes
0answers
22 views

Question about asymptotic analysis comparing two functions

I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$ Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \...
4
votes
2answers
187 views

Linear algorithm to measure how sorted an array is

I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I'...
0
votes
1answer
38 views

Why N-Queens Problem is not used as experiment in CSP thesis?

I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems. If so,when I do master ...
0
votes
1answer
28 views

Analysis of dependent double for

Here is the algorithm: int sum = 0 for (int i = 2N; i > 0; i = i / 4) { for (int j = 0; j < i; j+=2) { sum++ } } I figured this would be ...
0
votes
0answers
25 views

How do I calculate the work for a parallel algorithm?

I have problem (for HW) which asks to find a sequential and parallel algorithm to check if a given set of cubes is stacked on top of each other or not. The conditions provided are that the stacks must ...
0
votes
1answer
35 views

Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

Given a set of positive integers : $ \\ D = \{ D_1, D_2, ..., D_n\}$ and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find ...
1
vote
1answer
25 views

Is the sieve an improvement for prime finding over an optimized algorithm?

I don't think it is, as you have to loop through each set multiple times at least. implementation of sieve in JS - in the answer at the bottom. The link shows a 10X improvement using sieve. In this ...
0
votes
1answer
22 views

F-measure with $\beta > 1$

Consider the F-measure $F_{\beta}$. I know that with $\beta < 1$ precision is given more importance, ending with $F_{0} = precision$. With $\beta > 1$ means recall gets the upper hand, with the ...
0
votes
1answer
37 views

Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
0
votes
1answer
34 views

Number of permutations of set {1, 2, …, n} for which insertion sort will perform exactly n permutations

I have had the following problem at my last exam: For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons. My thinking ...
0
votes
2answers
76 views

Is this program O(n^2logn) or O(nlog^2(n))?

I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $O(n^2 \log(n))$ or $O(n\log^2(n))$ or something else entirely. ...
1
vote
1answer
31 views

Maximum Subsequence Sum : Mark Weiss:

In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"? By ...
2
votes
1answer
91 views

Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge

Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles,...
0
votes
1answer
28 views

Uniqueness of non-dominated two-dimensional points

This question is a nice variant of How to compare n number of m-dimensional points among one another with minimum time complexity? for two dimensions. We say point $p_i=(x^i_1, x^i_2)$ dominates ...
2
votes
1answer
28 views

Demonstrating that probability for every possible result is uniform at the end of an algorithm

I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$. At ...
1
vote
2answers
76 views

What is the time complexity of this “reverse words” algorithm?

I had to write an algorithm that, given the input ['h', 'a', 'r', 'd', ' ', 'i', 's', ' ', 'c', 's'] would return ...
2
votes
1answer
78 views

Kirchhoff's Spanning Tree Algorithm

Recently I have studied Kirchhoff's spanning tree algorithm to count the number of spanning trees of a graph, which has the following steps: Build an adjacency matrix Replace the diagonal entries ...
2
votes
1answer
112 views

How to compare n number of m-dimensional points among one another with minimum time complexity?

Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
1
vote
0answers
38 views

Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$

In a hypothetical world, we have a machine that can find median of $n$ numbers in $O(\sqrt{n})$. (Of course this machine is not real). Can we use this machine to sort an array in $O(n)$? I don'...
0
votes
0answers
29 views

Proof: Quick Sort Is $O(n*logn)$

I was given the follow proof: $$T(n)=n+2T(\frac{n}{2})$$ Will prove that $$T(n)=O(n*logn)$$ For $2:$ $$T(2)=2+2T(1)=2\leq 2*log(2)$$ Assume it is correct for $n-1$ in particular for $\frac{n}{2}$ ...
0
votes
0answers
15 views

How to detect self loop in graph using greedy algorithm if given list of number of degrees

if you are given list of n integers that represents the degree of a graph. How to detect if there self loop in the graph using greedy algorithm.
3
votes
1answer
75 views

Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $. I´ve made a program to check this statement and it ...
0
votes
1answer
133 views

Why is my algorithm version so slow with this input?

Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (...

1
2 3 4 5
33