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.

6
votes
2answers
75 views

Is $\lceil\log n\rceil!$ polynomially bounded?

Considering the definition, $f(n) = O(n^k)$, for some constant $k$. If I choose $k = 100$ and plot, it shows $n^{100} > \lceil\log n\rceil!$ for all $n > 1$. However, the solutions to ...
1
vote
1answer
37 views

How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)

Can someone tell me what am I doing wrong? Problem: https://codeforces.com/contest/22/problem/B Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) ) Eg: ...
0
votes
0answers
37 views

What is a uniform algorithm?

what is a uniform algorithm? I see some definitions based on running time, but also contradictory uses of slower uniform algorithms.
0
votes
0answers
33 views

$\Omega$-notation for insertion sort [duplicate]

I'm reading the CLRS book and there is a statement for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ ...
1
vote
0answers
29 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as $$C U_{a^{2}}(|c\rangle|y\...
0
votes
1answer
30 views

Finding the maximum disjoint weight in a weighted node graph

I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the ...
1
vote
0answers
30 views

Hypergraph sorting computational complexity

For a hypergraph, I want to know the computational complexity of this step in my algorithm what is the computational complexity of this kind of sorting Sort the hyperedges in descending order based ...
2
votes
0answers
30 views

Analysis quickselect: Median of Medians with duplicates

in This Lecture Notes 1 (page 3), it is said concerning quickselect with median of medians: If there are repeated elements ... Alternatively, one has to refine the algorithm and the analysis ...
2
votes
1answer
30 views

Conditions for maximum period of quadratic congruential method (PRNG)

$X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$ Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"): $c$ ...
0
votes
0answers
9 views

Shortcuts/Patterns for being able to calculate the running time of a loop/algorithm? [duplicate]

This is my first question here. I, like many people, suffer from the lack of the ability to be able to determine the running time of algorithms just by looking at them. I've picked up on a few ...
0
votes
2answers
88 views

Why run -time of N-Queens using backtracking algorithm fluctuates?

I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$. I think the ...
3
votes
1answer
92 views

How to understand the recurrence relation and time-complexity of StoogeSort?

I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the ...
3
votes
2answers
96 views

Bubble Sort with “while” loop - why is average case n^2?

If Bubble Sort is written as: ...
2
votes
1answer
86 views

Subtree with minimum sum of nodes' costs

Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that ...
4
votes
1answer
39 views

How to approach analysis of randomized algorithm

Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
0
votes
1answer
25 views

Proof Big Theta (sum of a geometric)

Here sum of a geometric, where c is a positive real number. $g(n)=1+c+c^2+...+c^n$ $\theta(1)$ if $c<1$ Any idea to solve this?
0
votes
1answer
29 views

Big O of runtime operation n-m+1 [duplicate]

I have a loop that runs n-m+1 times where m = len(list_m) n = len(list_n) for i in range(n-m+1): Is this time complexity O(n-m+1)?
0
votes
0answers
15 views

Min Cut Algorithm using Randomly inserted directions

I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones). My ...
0
votes
1answer
33 views

Is it possible to compute how many iterations this algorithm will take?

I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always ...
2
votes
2answers
379 views

All superlinear runtime algorithms are asymptotically equivalent to convex function?

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$? All the examples that I could think of satisfy the above ...
1
vote
1answer
28 views

Time complexity of finding subsequences of a string segmented into parts

Let $S$ be a string of length $N$, consisting of digits 0 to 9. For convenience, we assume $N$ to be a multiple of 3. Then, we split $S$ into $N/3$ equal parts, each of length 3. For each equal part,...
1
vote
1answer
47 views

What is the complexity of this prime trial division algorithms?

I have two algorithms. What are their time complexities? The first algorithm checks the modulo of all odd integers from $3,5,...\sqrt{n}$. The second algorithm generates a list of prime from $2,3...,\...
1
vote
1answer
32 views

What does it mean when saying “we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$”?

What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? (it appears on the top of page 12 of this paper)
1
vote
1answer
66 views

Why does $O(n \log n)$ seem so linear?

I've implemented an algorithm, that when analyzed should be running with the time complexity of $O(n \log n)$. However when plotting the computational time against the cardinality of the input set, ...
2
votes
2answers
120 views

Constant factor of an array

In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41: Insertion into a full array can be handled by resizing, i.e., allocating a new array with ...
0
votes
0answers
26 views

Question on preventing k from reducing too quickly during KMV intersection

This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data. The way it does it is to first map the stream of data to a space that almost ...
1
vote
1answer
24 views

Complexity of set partition generation while equivalence relation is given

Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this ...
3
votes
1answer
490 views

Complexity of many constant time steps with occasional logarithmic steps

I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant. Is it possible for this task to ever take ...
0
votes
1answer
38 views

How to count the biggest size of the problem during some time period?

We assume that time of solving the problem $=f(n)$$\mu$s. Now we have to calculate how big problem we can calculate for each time periods. So there are: $\lg n, \sqrt{n}, n, n\lg n, n^2, n^3, 2^n, n!$...
1
vote
1answer
61 views

Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes

I was tasked with finding a way to decide the language $A=\{0^k1^k \mid k\ge 0\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was ...
1
vote
1answer
60 views

Which algorithm is this?

I'm looking for someone who can tell me which algorithm this is and help me to clearify what the variable mean. $g_j$ : the shortest path length from $1$ to $j$ $t_{i,j}$: the length from $i$ to $j$ $...
5
votes
1answer
162 views

Worst-case input for median-of-medians with groups of size 3

Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a ...
0
votes
2answers
47 views

Does my solution converge to O(N) for worst-case time complexity?

Forgive me if this should be in StackOverflow or Mathematics instead! I was given the following question at an interview: ...
2
votes
1answer
54 views

Expected number of iterations for bozo sort opt algorithm

I'm trying to figure out the upper bound for the number of iterations of the bozo sort opt algorithm, described in this paper on section 3.2: http://www.hermann-gruber.com/pdf/fun07-final.html I know ...
2
votes
1answer
45 views

Lemma R of section 3.2 (The Art of Computer Programming)

In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $\lambda = p^e$ which means: $$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$ The ...
2
votes
1answer
72 views

How do I describe formally complexity of 2-sum problem algorithm?

I have algorithm that finds if there are two elements in sorted array that have sum zero. ...
1
vote
1answer
146 views

Why don't integer multiplication algorithms use lookup tables?

It seems to me that we can use lookup tables for multiplication of two integers of size $\log(n)/2$, and that the number of entries for each table of these numbers should be $O(n)$. Now, multiplying ...
3
votes
1answer
33 views

How good (or bad) is my makeshift PRNG?

Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I ...
1
vote
1answer
65 views

general question amortized cost and worst case

lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1). ...
4
votes
0answers
68 views

Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized

I have a question about my solution to a problem from Hackerrank. The problem is, given $R,C,H,W$ with $1\le R,C\le 100$, $1\le H\le R$, $1\le W\le C$, an $R\times C$-matrix $L$ and an $H\times W$-...
1
vote
0answers
55 views

Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
1
vote
1answer
28 views

What are the k-collections described in ch. 8 of “An Introduction to the Analysis of Algorithms” by Sedgewick

In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425. My confusion is how to identify the k-...
-2
votes
1answer
36 views

FSM (Finite State Automaton and PDA (Push Down Automaton

Say we have the following language, some number of a's and b's followed by three a's followed by some number of a's and b's Show how you can create a finite state machine that will accept the words ...
0
votes
0answers
160 views

Brute Force Approach for LCS and its Time Complexity

I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am ...
3
votes
1answer
75 views

Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
0
votes
0answers
38 views

Correctness of algorithm and its complexity

I am trying to solve problem of generation of so called activity-on-edge (activity-on-arc) network graph given based on given activity-on-node network graph. So, I found this paper proposing an ...
0
votes
1answer
34 views

algorithm analysis - complex dependant nested loop

First of all, I know there are many questions like this on the site. But I think this case is a bit different. Consider the following code: ...
3
votes
2answers
206 views

How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$. Note that ...
1
vote
0answers
19 views

Numbers choosing algorithm form constants according to input [closed]

First of all sorry for my poor English. Problem: There are 15 strings 1 to 50 and they’ve defined randomly. There is a input 1 to 500. This 15 strings are static but input is changing during 75k ...
0
votes
0answers
15 views

What would be the line by line analaysis and construction function T[n] with Big Oh notation? [duplicate]

What would be the line by line analaysis and construction function T[n] with Big Oh notation? Thanks a lot.