# Tagged Questions

39 views

### Finding a better algorithm for a problem [closed]

Interval scheduling. Job j starts at sj and finishes at fj What is the best way to solve this?
173 views

### Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?

The worst case running time of insertion sort is $\Theta(n^2)$, we donâ€™t write it as $O(n^2)$. $O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of ...
68 views

### Common Algorithms without Asymptotically Tight Bounds

I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
374 views

### What are the characteristics of an $O(n \log n)$ time complexity algorithm?

Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible ...
98 views

### What is the complexity of this matrix transposition?

I'm working on some exercises regarding graph theory and complexity. Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
139 views

### Running time of a nested loop with $\sum i \log i$ term

So I have the following pseudo-code: Function(n): for (i = 4 to n^2): for (j = 5 to floor(3ilog(i))): // Some math that executes in constant time So ...
69 views

### Computational complexity of the clique problem

What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?
185 views

I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis? What I understood: Let say we have 3 three operations a,b,c used 1,2 and 3 times ...
180 views

### Iterative binary search analysis

I'm a little bit confused about the analysis of binary search. In almost every paper, the writer assumes that the array size $n$ is always $2^k$. Well I truly understand that the time complexity ...
166 views

### Comparing Time complexity?

How would I solve these problems involving time complexity: Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs ...
73 views

### What is the complexity of Hoffman and Pavley's Nth best path algorithm?

I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
98 views

### How does this recurrence relation fit the algorithm?

I have the following pseudo code: ...
301 views

338 views

### Brute force Delaunay triangulation algorithm complexity

In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the ...