# Tagged Questions

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.

10 views

### What is the time complexity of min-heap based solution to calendar rendering problem

Question: You are given a set of events in a day. Each event has a start and end time. Find the maximum number of concurrent events Solution: First convert events into an array of "Event ...
41 views

### What is the complexity of Array[n] and Object.value

I faced a great doubt about the Complexity of two ways of calling a information. First I have an Array, if I call an array in a program like this: print array[0] ...
71 views

### Estimating the complexity of an algorithm by looking at code

Time complexity seems rather a difficult notion for people who were not professionally trained in math or computer science. I understand it informally and can high-level compare which one is better ...
14 views

### TicTacToe Solver [on hold]

I want to find the most efficient algorithm for determining whether there is a winner on a board of tictactoe at the end of the game. Normal tictactow board dimensions are 3x3 but I need the most ...
31 views

### Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how many permutations would get rejected ...
23 views

### Maximal Independent Set [on hold]

Regarding algorithms to find maximal independent set in an unweighted and undirected graph: I saw many articles online that are referring to the case of which every vertex has a maximal degree of d, ...
46 views

### Stack depth for QuickSort

CLRS Problem : 7.4 How does Tail-Recursive-QuickSort improve the efficiency of quick sort any better ? Original quicksort Tail recursive quicksort ...
53 views

### How do i proceed with writing the algorithm? What will be the run time of the algorithm?

Given an n x n matrix which is to be multiplied with a vector of size 1 x n, write a algorithm for the purpose with 1-D partitioning of the input matrix along with one element of the vector per ...
35 views

### Why does using unary in subset sum problem result polynomial time complexity?

From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input). The number of bits in binary notation is obviously less ...
38 views

### PageRank algorithm analysis

I was reading a paper about the PageRank algorithm and it mentions $2$ ways to compute the weighted score for each vertex: If $M_{n \times n}$ is a positive column stochastic matrix that ...
80 views

### Time complexity of Depth First Search

Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about. I ...
106 views

### Algorithm with no closed-form exact complexity

Does there exist an algorithm for which an exact complexity provably cannot be expressed in closed-form? Here closed-form means a finite composition of addition, subtraction, product, division, ...
27 views

176 views

### How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
26 views

### Converting pseudo code to a recurrence relation equation? [duplicate]

The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series. Pseudo code is below. I have so far T(...
105 views

### What is the compleixty of this algorithm?

The algorithm is as follows: a = rand % a random number between 0 and 1 b = a while b == a b = rand end Here rand is a ...
54 views

### Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
54 views

### Convergence of recursive formula in TextRank

I am reading a paper about the TextRank algorithm in keyword extraction and they mention the recursive formula:  \displaystyle S(V_{i}) = (1 - d) + d \ast \sum_{j \in In(V_{i})} \frac{1}{|Out(V_{j})|...
91 views

### Why do we use multiple data structures? [duplicate]

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees. Both runs in worst case O(n) in the same operations, so why don't we use only ...
30 views

### Amortised analysis of a simple loop and 3 operations

I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$. Operation OP(S,X[i]) has complexity ...
51 views

### What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
37 views

### Why should small o notation has to satisfy the equation for all values of the constant

Big-O of a function i.e. f(n) = O(g(n)) is such that both c and $\textbf{n}_0$ can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the ...
131 views

### Why is b-tree search O(log n)?

B-tree is a data structure, which looks like this: If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I ...
146 views

### My algorithm is different from CLRS' — is it wrong?

Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states: Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines ...