# 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,948 questions
Filter by
Sorted by
Tagged with
4 votes
1 answer
146 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
4 answers
101 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
1 answer
123 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: ...
• 163
-2 votes
1 answer
49 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
1 vote
1 answer
129 views

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

According to DFS algorithm for graph traversing: ...
• 163
2 votes
1 answer
63 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 ...
1 vote
2 answers
296 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 "...
• 21
1 vote
1 answer
134 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 ...
• 21
1 vote
1 answer
79 views

Text: ...
2 votes
2 answers
466 views

### Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of 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 ...
• 21
2 votes
1 answer
112 views

• 123