# 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.

1,900 questions
Filter by
Sorted by
Tagged with
17 views

### Considering definitions as equalities, what would happen if you continually substituted a word’s definition?

I’ve had this question for several years now but have next to no programming experience, nor good connections to anybody who does. So I decided to see if stack exchange had an answer. The idea is to ...
73 views

### Is $m \log^2 n$ complexity too much?

I have been struggling for a few hours in terms of finding the right solution for the following problem: Suppose we have a file that contains integers where each represents a user of a service. By ...
• 205
1 vote
55 views

### Time Complexity of Exponentiation Operation as per RAM Model of Computation

Now, $\color{blue}{\text{Exponentiation}}$ is defined as Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and ...
• 219
176 views

### Amortized analysis on a dynamic table that grows its size by $\sqrt{size}$

The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS Problem: We are given a dynamic table $T$ that supports INSERT operation, ...
• 211
118 views

### Sorted list of counters in constant time

Summary. A data structure maintains in constant time a sorted list of counter values, for a dynamic set of counters. I am interested in references using this structure, and in possible improvements. ...
34 views

### Arithmetic intensity of matrix multiplication

Arithmetic intensity (AI) is the number of FLOPS divided by the number of byte accesses. For conventional matrix multiplication of matrices of sizes $m \times k$ and $k \times n$, the number of FLOPS ...
• 11
27 views

### Understanding MTD-f

In the MTD-f algorithm: ...
• 123
1 vote
21 views

### Worst case lower bound of the general number guessing problem

I have the following problem: Let Alice and Bob be two people playing games. Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
16 views

### Is $\frac{opt}{c}(1-\epsilon)$ for some constant c >0 considered a PTAS?

So I am studying PTAS algorithms. For a maximazation problem the difinition says that an algorithm that has value A , is a ptas if : $A \geq opt(1-\epsilon) \; ,\forall \epsilon > 0$ (and I guess ...
• 191
31 views

### Find matrix local minimum - two analysis which seem to get contradictory runtimes

Suppose you have an $n\times n$ matrix and you want to find a local minimum. To find it you scan the middle row and column and identify a minimum. If it is a local minimum, you're done; if not, you ...
• 283
1 vote
17 views

### Deterministic Algorithm for searching for object $d$ units down one road in a $k$ road intersection

Suppose we are at the centre of a $k$ road intersection (i.e, there are $k$ different roads radiating out from where we are standing, infinitely). Suppose along one of these roads is a treasure. This ...
1 vote
44 views

### Simplifying Notations in Recurrence Relation

In the CLRS book, section 4.4 they try to resolve the following recurrence: $$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$ Later, they write the same recurrence as T(n) ...
• 200
1 vote
26 views

### Do I need to learn probability for CLRS?

I am currently learning Discrete mathematics. there is a topic on dicrete probability (which I havent covered yet), but I also know there is non-discrete probabiltiy but I dont know what they really ...
• 11
1 vote
42 views

### Formal definition of algorithm runtime

In the analysis of algorithms textbooks that I've seen, as far as I could tell, the runtime of an algorithm is defined intuitively. Is there a simple formal definition of this concept? I.e. a ...
• 3,464
53 views

### Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested. The first algorithm uses "a constant amount of memory, regardless of the length of the string.&...
1 vote
37 views

### Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
• 191
29 views

### bellman ford and dijkstra sparse vs dense graphs

I believe using big o notation that Bellman-Ford is to be expected to be faster on sparse graphs and dijkstra's should be expected to be faster on dense graphs, but in practice dijkstra's is always ...
1 vote
27 views

### Analogue computers

Since every continuous variable can be sliced into many discrete values, is there a particular class of problem that can only be solved by an analogue computer?
• 11
32 views

### Partially correct?Totally correct?Deterministic?Determined?Terminating? What do these adjectives mean for an algorithm?

These terms are often used to describe algorithms but I'm not really sure what they mean. I would like to see more examples of what each one is like and how they can be identified. Can anyone please ...
83 views

### Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting ...
1 vote
47 views

### uniformly distributed edge weights in an MST

Suppose that the edge weights in a graph are uniformly distributed over the halfopen interval [0, 1). The question is, how can one sort the edge weights in linear expected time? I know the ...
1 vote
77 views

### How to tell if I know algorithms & I learned it right?

Notes I apologize if the question is not formed well, I tried my best. "Only" means anything else is discarded. A stupid man’s report of what a clever man says can never be accurate, ...
1 vote
25 views

### How to count this operation for (int interval = n/2; interval > 0; interval /= 2) using counting primitive operation?

I was confused how to label this for (int interval = n/2; interval > 0; interval /= 2) with counting operation and estimating this operation so that I can get ...
• 23
1 vote
34 views

### Proving the least number of operators required equals $min((x-target)*2, (target*2)-1)$

Here is the source for the problem below: https://leetcode.com/problems/least-operators-to-express-number/discuss/1675169/java-or-recursion-or-greedy-or-math For completeness, below is the problem ...
2k views

### "Guess the number" Problem on Turing machines

I am currently learning about the concept of Turing Machines and trying to relate it with my knowledge on the application of the Binary Search algorithm. The problem I am working on is to write an ...
103 views

### Analytic combinatorics and less-precise running times

Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
• 315
1 vote
26 views

### Big theta and big 0 bounds for iteration method and Master Theorem

In Algorithms 1, I'm noticing that big-Theta running times are always used for recurrence relations when using the iteration method. Meanwhile, using the Master Theorem always seems to result in a big-...
• 111
1 vote
50 views

### Tight bound for T(n) = T(n/2) + T($\sqrt{n}$) + n

I have seen examples of how to find the solve the recurrence for T(n) = T($\sqrt{n}$) + n, but how do we go about if there is another T(n/2) in there? So I tried to unfold the recurrence out and this ...
• 21
1 vote
43 views

### Polynomial algorithm for the «Input Series» Problem

Can you help me design an algorithm to solve the following problem in polynomial time? Let n be a given natural number. We define an input series of length n to be a string of length n which is built ...
48 views

### How to solve T(n) = T(n-1) + n(n-1)?

I am not able to solve the following recurrence relation: T(n)={T(n−1)+n(n-1) if n≥2,T(1)=1.
42 views

### Which of these algorithms will involve the least amount of math?

I'm taking an algorithms class for my computer science degree, and one of the requirements is to research and present 3 different algorithms. The only problem: linear algebra wasn't a prerequisite to ...
1 vote
68 views

### Why is the input of the algorithm in "Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation" a matrix?

My question is about the algorithm in the article Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation, as described in the picture below. It is written at beginning ...
• 139
28 views

### Summing of time complexities into one single representation

Background I have some code, I have written. The time complexity for building the Graph with Nodes + connections is calculated ...
• 125
1 vote
66 views

### Subtraction on Big Theta notation

This is a question I got for an assignment, and I have been stuck on it for the past few days. Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$ Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$ I ...
27 views

### Sum of asymptotic notations

Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$? Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
• 13
113 views

### Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
13 views

### Detect the actual edges of circle in directed graph [duplicate]

Okay so , I know how bellman -ford can detect a negative circle. My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the ...
• 191
1 vote
51 views

### reduction from 3SUM to 3ARR-ARITH

The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist $i,j,k\in \{1,\cdots, n\}$ so that $A[i] + A[j]+A[k] = 0$. The 3ARR-ARITH problem is defined ...
28 views

### Sum of a function Θ(g) with a function that is not O(g)

Consider g a function of n: $g(n)$. Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about \$f(n) + ...
• 13
1 vote
105 views

### Check Welzl's algorithm time complexity

From the wiki this is the algorithm and we know that final complexity is O(n) but how we reached to this , is my problem : ...
68 views

### Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?

Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the ...
• 167
106 views

### Warnsdorff's rule: more errors with odd sized boards

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
• 167
1 vote
86 views

### Having a lot of trouble trying to reason the formal definition of Big O

My professor recently brushed over the formal definition of Big O: To be completely honest even after him explaining it to a few different students we all seem to still not understand it at its core. ...
1 vote
43 views

### Shamos algorithm , cannot understand the Area part

I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia: ...
34 views

### Need the time complexity of this conditional statement method

My idea of the program is : Input = n sets objective function ObjFn equals to O(n^3) Output = the order of n sets Steps: Applying ObjFn to all n sets Choose the n of the Minimum ObjFn to be ordered ...
• 1
20 views

### what is the running time of this while loop? [duplicate]

Hello i have a piece of code like this: ...
1 vote
57 views

### Finishing Time in DFS, is that necessary?

According to DFS algorithm for graph traversing: ...
61 views

### Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?

I'm a computer science bachelor student tasked with understanding On the ICP Algorithm by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious ...
• 75