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
-2
votes
1answer
24 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 ...
0
votes
0answers
20 views

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

Hello i have a piece of code like this: ...
-3
votes
0answers
13 views

recurrence equation 2T(n-4) + n^2 solution?

need help solving this equation. the general equation I end up with: 2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]
1
vote
1answer
30 views

Finishing Time in DFS, is that necessary?

According to DFS algorithm for graph traversing: ...
2
votes
1answer
55 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 ...
0
votes
0answers
16 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?
0
votes
2answers
33 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 "...
1
vote
1answer
13 views

Unstable nature of Lomuto partition scheme

In undergrad Quicksort implementation, Lomuto partitioning scheme is used. We are taught that Quicksort is an unstable partitioning algorithm which is cause of the extra swaps that occurs even when ...
2
votes
2answers
56 views

Given n positive integers, pick two elements and subtract each by one with one operation. Find max operations

Problem Description: we have an array of n positive integers and in one operation we have to choose two elements in the array and decrease them by 1. (Elements on which we are performing this ...
2
votes
1answer
53 views

Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$

Text of the problem: Solve the following recurrence equation and prove it by applying the principle of induction: $T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \...
2
votes
1answer
127 views

What is the meaning of the statement "a sequence of n PUSH, POP and MULTIPOP opreations"

I am reading CLRS 3rd Ed, chapter 17.1 (Aggregate analysis pg453) and I came across this statement. Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack. I ...
4
votes
1answer
363 views

Is there some kind of expected error margin for my Monte Carlo algorithm?

My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the ...
1
vote
0answers
31 views

Mistake in potential function for dynamic table contraction in CLRS?

In the third edition of "Introduction to Algorithms" by Cormen et al ("CLRS"), section 17.4 ("Dynamic tables") is an overview of amortized analysis as it relates to ...
0
votes
1answer
62 views

How can we construct algorithm to evaluate logarithm of a real positive number

How can we construct the algorithm to evaluate the logarithm of a real positive number bit by bit in the base 2 system? I have first expressed any number as $x\cdot2^n$, where $x \in [1,2]$, by ...
2
votes
1answer
49 views

What is an O(n)-approximation?

I see the following notations used: $O(1)$-approximation $O(n)$-approximation $\Omega(n)$-approximation Can someone please explain what they mean? I know what an approximation is with a normal ...
0
votes
1answer
26 views

Considerations for space complexity analysis

There is a lot of information on time complexity analysis. For example, we know that for calculating the time complexity we study the number of operations (e.g. traversal, swapping, comparisons etc.) ...
0
votes
1answer
45 views

Time Complexity Analysis When Merging Routes in Vehicle Routing

I would like to know the best way to approach the time complexity analysis of the following algorithm. I have come up with 2 approaches so far. We have a ...
1
vote
1answer
44 views

Maximum flow in integer flow network

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
1
vote
1answer
52 views

Traversing a directed graph with negative weights

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
1
vote
1answer
28 views
0
votes
0answers
26 views

Is there a Linear Transformer which uses only Matrix operations?

I am interested in finding a Linear Transformer which only uses ONLY matrix operations (more specifically matrix-matrix multiplications during training and matrix-vector multiplication in inference ...
0
votes
0answers
19 views

What is the best linear transformer?

I apologize but I couldn't find the reference about the fact I want to ask... I have read in the abstract of a paper which I don't remember the title the following fact: (I also have google a lot ...
0
votes
0answers
14 views

change an algo to obtain optimal run time

I have an algorithm that does the reverse of partition ...
1
vote
1answer
26 views

Is the transformer SLiM compatible with ALBERT?

My question is about the article Sub-Linear Memory: How to Make Performers SLiM. It is written in the article "our algorithm is compatible with distillation (Sanh et al., 2020)". Now I would ...
2
votes
4answers
135 views

Why was the fast inverse square root algorithm so ingenious?

In 2005 ID software open source the game Quake 3 Arena. When they did it was discovered was an algorithm that was so ingenious and all it did was calculate the inverse of a square root. The easy way ...
0
votes
0answers
17 views

the convergence of the iterative algorithm has a major problem

In order to solve an optimization problem, I divided the main problem into two sub-problems. The two sub-problems require to be solved iteratively until the algorithm converges. I use the bi-section ...
0
votes
1answer
46 views

Bin packing problem and optimality proof

Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w_i\in W$ is stored before $w_j\in W$ then ...
0
votes
0answers
18 views

Is it possible to run the transformer (performer) SLiM without using GPUs?

This question is about the article Sub-Linear Memory How to Make Performers SLiM. I googled for the fastest transformer and I think almost surely I found. It is called SLiM. The problem is the authors ...
0
votes
1answer
40 views

prove sub array has a definite form with distinct end point integers

An array has elements from set {0, 1, 2}. A span SP of an array is any interval [start S, end E] such that the sub array must contain all elements from {0,1,2}. For example: in Array A = (0,1,0,1,1,2,...
0
votes
1answer
27 views

Return indices in the two sum problem

Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices ...
1
vote
1answer
60 views

How can I optimize the systems in the paper "Ensembling Ten Math Information Retrieval Systems"

My question is about the paper Ensembling Ten Math Information Retrieval Systems. I already know the algorithms in the paper can answer questions only using dot products (look the post). How can I ...
0
votes
0answers
37 views

Where is the bottleneck of CompuBERT?

This question is about CompuBERT (new implementation). The average query time is less than 10 seconds. If I had made a good search on google PROBABLY the embedding phase takes 1 second and 0,1 second ...
0
votes
1answer
76 views

hash-tables - Expected-time for an unsuccessful search

The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c. Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
0
votes
0answers
34 views

Solving $T(n) = T(0.01n) + T(0.99n) + cn$ [duplicate]

How to solve the below relation? $$ T(n) = T(0.01n) + T(0.99n) + cn $$ This will not be a balanced tree. For $k$ levels I have something like $\bigl(\frac{1}{100} + \frac{99}{100}\bigr)^k \cdot cn$. I ...
0
votes
1answer
95 views

What could be the most efficient algorithm to find index in an array that matches given conditions?

I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A[j-1]>=A[j]<=A[j+1]. Example: ...
0
votes
1answer
47 views

Inversions of Insertion Sort and Bubble Sort

An array with bubblesort time $\Theta(n)$ is nothing but a sorted array like: A = 1 2 3 4 5 No swaps are done so only $n - 1$ comparisons. An array with insertionsort run time $\Theta(n^2)$ is a ...
0
votes
2answers
46 views

inversions in array

If the worst case arrays {5 4 3 2 1} have number of inversions as Θ(n^2) => n(n-1)/2 swaps The best case arrays {1 2 3 4 5} have number of inversions 0(no swap) What kind of arrays have number of ...
0
votes
1answer
31 views

sort is equal to inversions logic

In Bubble sort, the number of swaps/comparisons is equal to the number of inversions. 1st pass it will do (n -1) comparison 2nd pass it will do (n-2) comparison....so on (n-1)n = n^2 - n Worst case ...
0
votes
1answer
28 views

simplified into asymptotic notation

I have a function that needs to be represented in theta form. The below is my answer. But the correct answer is 𝜃(n.2^n) Can someone please explain me how??
0
votes
0answers
24 views

Amortized Analysis of extract-min-operation of Fibonacci Heap

I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is: The potential before ...
10
votes
2answers
4k views

Can I multiply Big-O time complexities?

Can I multiply Big-O time complexities? For example: $O(n) \cdot O(n) = O(n^2)$? UPDATE: The question came from my observation that different sources analyze their algorithms in different ways. For ...
0
votes
0answers
56 views

Analyzing Hybrid Merge and Insertion Sort

We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case. The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small ...
1
vote
1answer
81 views

Prove that the following algorithm for division and remainders of natural numbers is correct

I am currently brand new to the correctness proof method, and have stumbled upon this algorithm which I find very tricky. Prove that the following algorithm for division and remainders of natural ...
1
vote
1answer
23 views

Complexity of checking graph separation

Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
0
votes
0answers
167 views

Some Confusions in Ricart Agrawala second algorithm-token based algorithm for mutual exclusion

Resources that I followed to learn-: http://www.ejbtutorial.com/lectures/petru/lect6-7.frm.pdf https://cis.temple.edu/~wu/teaching/Spring2020_CIS5644_Distributed_Computing/distributed-computing-2020-...
0
votes
0answers
16 views

Is ordering achieved by central server algorithm?

ME3 specifies that the first process be granted access before the second Ordering-: Requests are granted in the order they were requested. Colouris Distributed Systems book-: The reader should ...
0
votes
1answer
32 views

Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
0
votes
1answer
30 views

Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
1
vote
2answers
51 views

Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?

I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...

1
2 3 4 5
38