# 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,862 questions
Filter by
Sorted by
Tagged with
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 ...
20 views

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

Hello i have a piece of code like this: ...
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 ]
30 views

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

According to DFS algorithm for graph traversing: ...
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 ...
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?
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 "...
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 ...
66 views

Text: ...
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 ...
53 views

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