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
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 205
1 vote
1 answer
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 ...
user avatar
3 votes
1 answer
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, ...
user avatar
2 votes
1 answer
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. ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 11
2 votes
0 answers
27 views

Understanding MTD-f

In the MTD-f algorithm: ...
user avatar
  • 123
1 vote
0 answers
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}$ ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 283
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
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) ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 11
1 vote
2 answers
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 ...
user avatar
  • 3,464
0 votes
1 answer
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.&...
user avatar
1 vote
1 answer
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-...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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?
user avatar
  • 11
0 votes
1 answer
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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, ...
user avatar
1 vote
2 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
4 votes
6 answers
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 315
1 vote
0 answers
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-...
user avatar
  • 111
1 vote
2 answers
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 ...
user avatar
  • 21
1 vote
2 answers
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 ...
user avatar
-1 votes
1 answer
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.
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 139
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 13
0 votes
2 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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) + ...
user avatar
  • 13
1 vote
1 answer
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 : ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 167
4 votes
1 answer
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 ...
user avatar
  • 167
1 vote
4 answers
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. ...
user avatar
1 vote
1 answer
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: ...
user avatar
-2 votes
1 answer
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 ...
user avatar
  • 1
0 votes
0 answers
20 views

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

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

Finishing Time in DFS, is that necessary?

According to DFS algorithm for graph traversing: ...
user avatar
2 votes
1 answer
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 ...
user avatar
0 votes
0 answers
19 views

How to read the optimal makespan

Hello I'm having trouble reading the optimal makespan of job scheduling algorithm. In particular what does it mean for max to have index i here?
user avatar
1 vote
2 answers
121 views

How can you have an upper and lower bound on the worst-case complexity of an algorithm?

Yesterday I started reading "An Introduction To The Analysis of Algorithms" by Sedgewick/Flajolet. For me it was not clear what he meant with "theory of algorithms" and the "...
user avatar
  • 21

1
2 3 4 5
38