Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
8 views

Compare speed of two algorithms using big-oh notation

How do you prove the truth of such statements? All $\Theta\left ( n^2 \right )$ algorithms are faster than all $\Theta\left ( n^3 \right )$ algorithms. An $O \left ( n^2 \right )$ algorithm will ...
3
votes
0answers
27 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$-...
0
votes
0answers
38 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
26 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
22 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
36 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
49 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
33 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
25 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
45 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
16 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 ...
-1
votes
0answers
19 views

What is the time complexity for this program [duplicate]

What is the time complexity for this program. Select the right answer: A- $\Theta(n\log{n})$. B- $O(\log{n})$. ...
0
votes
0answers
13 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.
2
votes
1answer
47 views

Merging of two increasing binary trees why do we exchange left and right subtree

We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees. One way to merge these kind of trees is as ...
0
votes
0answers
18 views

Greedy Approach without constraint and a feasibility function

We know that the Greedy Approach in general, picks an element from a set of candidate elements that satisfies a predefined criteria (selection function) and is added to the solution if it satisfies ...
0
votes
0answers
32 views

Finding runtime of a recurrence relation with a fractional power

Consider the following algorithm and find the tightest Big-$O$: Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$. If my runtime is $T(n)$, I have: Lines 1 ...
0
votes
3answers
59 views

What is the asymptotic complexity of the following code snippet?

for (i = 2; i < n; i = i * i) { for (j = 1; j < i / 2; j = j + 1) { sum = sum + 1; } } I know that the outer loop can run for a maximum of $n^2$ ...
0
votes
0answers
25 views

Knapsack approximation algorithm (weights scaling)

I am trying to prove the following Knapsack approximation algorithm, the problem definition: Input: A set $S$ of $n$ objects that contains weights and values: $w_1,w_2,\ldots,w_n$ (weights) $...
2
votes
1answer
23 views

Is $T(n^2) = Ω(n)$?

According to this link: We need the notation for the lower bound. A capital omega $\Omega$ notation is used in this case. We say that $f(n) = \Omega(g(n))$ when there exist constant $c$ that $...
0
votes
0answers
54 views

Successive shortest path without reduced costs

The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows : Successive shortest path (for minimum-cost flow) : while all flow is not ...
0
votes
1answer
200 views

Is my proof of my greedy algorithm to find subsequence correct?

Credit to KleinBerg and Taros Book Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
0
votes
0answers
32 views

Calculating makespan among several machines

I have a question about makespan calculation. I know that makespan formula is like this: Makespan = Time of completion of last job - Starting time of the first job but I can't figure out how we ...
2
votes
1answer
49 views

Djikstra algorithm analysis

My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that? Dijkstra algorithm pseudocode: ...
-1
votes
1answer
50 views

What would be the big-o time complexity of this scenario? [duplicate]

I am wondering what the time complexity of a for loop that increments the control variable, but also multiplies it inside the loop. For example ...
0
votes
0answers
14 views

metrics for evaluating the performance of a load balancing algorithm

I have proposed a load balancing algorithm for distributed systems which monitors the load on each device in this system and moves excess load from over-loaded device to less-loaded device. What are ...
0
votes
1answer
32 views

Large-scale string clustering

I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at ...
0
votes
2answers
43 views

Prove that the following algorithm has STOP property (number of steps is finite)

Prove that the following algorithm has STOP property. I am not sure if this term is widely know, so the definition of STOP property that I got during classes looks as follows: STOP property (for ...
0
votes
1answer
26 views

Find the computational complexity of the given program

int seq(int n) { if(n == 0 || n == 1) return n; return(seq(floor(n/2)) + seq(ceil(n/2)); } Find the computational complexity of the above program. ...
1
vote
2answers
52 views

Running Time of Sorting Algorithm

Determine the asymptotic running time of the sorting algorithm maxSort. Algorithm maxSort(A) Input: An integer array A Output: Array A sorted in non-decreasing order ...
0
votes
1answer
12 views

Calculating the average waiting time of tasks

I have proposed a load balancing algorithm for a group of homogeneous processing devices and now I want to measure the average waiting time to see if my algorithm is successful in decreasing the ...
1
vote
1answer
26 views

Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the ...
0
votes
0answers
40 views

Modifying BFS to Find the least transfer stop as possible

let's say that a map of a bus system is provide by as graph G. and each edge of this graph is colored to distinguish which of bus lines that edge is associated with. Come up an algorithm which ...
1
vote
1answer
32 views

Complexity of Estrin polynomial evaluation

The Estrin model for polynomial of degree $n$ is well known. But the reading of the Knuth (vol 2) or the original's paper Estrin do not help (or I miss it). I am not able to determine the complexity ...
2
votes
1answer
61 views

Running Time for Finding Maximum

Consider the algorithm findMax that finds the maximum entry in an integer array. Algorithm findMax($A$) Input: An integer array $A$ Output: The maximum entry of $A$ ...
1
vote
1answer
23 views

Number of min-cuts of a graph

It can be shown that every graph G has at most $\binom{n}{2}$ min-cuts. It follows from Karger’s algorithm Analysis. Is there a different combinatorial proof of this fact? Was this known before ...
1
vote
2answers
59 views

Detailed step of Dijkstra's algorithm performance analysis

Reading the book of Dasgupta-Papadimitriou-Vazirani.pdf about the performance of Dijkstra's algorithm on Page 118, we are given: 4.4.3 Running time At the level of abstraction of Figure ...
3
votes
1answer
68 views

Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|). Now let's modify ...
0
votes
0answers
105 views

Egg dropping problem

Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal ...
1
vote
0answers
19 views

Practicality of Algebraic Machine Learning Methods [closed]

Last year this article was released detailing a method of high level machine learning using methods found from abstract algebra, with seemingly amazing results and claims. However, since then I have ...
0
votes
1answer
54 views

Recursive factorial algorithm

I'm struggling to understand this factorial algorithm. ...
1
vote
1answer
53 views

Worst-case complexity in terms of n?

I have this algorithm taken out from the Manual of Algorithms Analysis: ...
2
votes
1answer
39 views

Complexity of brute force primality test in the number of digits

I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime ...
1
vote
1answer
25 views

Why theta(n^2) if m=floor(n/2) for Naive String-matching

I’m reading CLRS(Introduction to Algorithm, 3rd edition). In the chapter 32.1 about the naive string-matching algorithm, the book says the worst case running time is $\Theta(n^2)$ if $m = \lfloor \...
2
votes
1answer
80 views

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
5
votes
2answers
103 views

Return copy of array, each element product of all others, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows: Given an array $<a_1, \ldots, a_n>$ of fixed-...
1
vote
1answer
29 views

Proof of the master thorem case with floors and b = 2

This question is related to my previous one. Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b > 1$ and $f(n) = \Theta(n^{\log_ba})$. Then $T(n)...
1
vote
0answers
28 views

How much of the x86 instruction set does blender use? [closed]

I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
1
vote
1answer
42 views

Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)

I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ ...
1
vote
1answer
33 views

Polynomial time algorithm - Matching pairs of vertices

Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. ...
1
vote
1answer
46 views

Proving correctness of inefficient algorithm - Path between two vertices

Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity ...