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.

learn more… | top users | synonyms

0
votes
0answers
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 ...
1
vote
1answer
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] ...
1
vote
2answers
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 ...
0
votes
0answers
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 ...
5
votes
0answers
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 ...
1
vote
0answers
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, ...
-1
votes
1answer
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 ...
-5
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
6
votes
1answer
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 ...
3
votes
4answers
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, ...
6
votes
1answer
27 views

Showing strong connectivity is in DSPACE((logn)^2)

$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$ I've learned the following deterministic algorithm to solve the problem in $log^2n$ space: $\psi(G,s,t,k) :$ $\hspace{1cm}\...
1
vote
1answer
40 views

Vertex cover of a graph by removing leaf-vertices from a DFS tree

Question taken from "The Algorithm Design Manual" by Steven S. Skiena, 1997. A vertex cover of a graph $G=(V,E)$ is a subset of vertices $V'\subseteq V$ such that every edge $e\in E$ contains at ...
0
votes
1answer
58 views

Running time of naive recursive implementation of unbounded knapsack problem

How does one go about analyzing the running time of a naive recursive solution to the unbounded knapsack problem? Lots of sources say the naive implementation is "exponential" without giving more ...
1
vote
1answer
59 views

Long multiplication school method: number of primitive operations to calculate first partial product?

Having got some basics down in regard to addition and explaining it in terms of primitive operations (addition and multiplication), I am now again stuck on understanding the more complicated long ...
0
votes
0answers
15 views

Amortized cost of decimal counter

Can somebody tell me what the lowest amortized cost for the increment operation of a decimal counter is? I can show the costs are O(1) and with max amortized costs of 2 (similar to a binary counter), ...
-1
votes
1answer
50 views

Which is the most efficient out of Bubble Sort, Selection Sort, Insertion Sort for a identical set of elements?

Which of the sorting algorithm is (classical implementation with no enhancements) the fastest for a data set with all identical elements? And why? How would one justify the answer to the above ...
1
vote
1answer
48 views

Dijkstra's algorithm runtime for dense graphs

The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges. Since $E \sim ...
9
votes
2answers
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 ...
-1
votes
1answer
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(...
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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})|...
2
votes
3answers
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 ...
3
votes
1answer
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 ...
-3
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
5answers
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 ...
4
votes
3answers
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 ...
0
votes
2answers
49 views

With Memoization Are Time Complexity & Space Complexity Always the Same?

I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
2
votes
1answer
65 views

Why isn't selection sort O(n log n)?

We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \...
0
votes
0answers
22 views

Amortised complexity of dynamic array using potential function

I'm trying to find out how potential function works. I'm trying to compute an amortised complexity of $n$ operations on dynamic array. To make it simple, assume, that we can't delete items and we can ...
6
votes
1answer
104 views

Is EXPTIME “solvable” or “checkable” in exponential time?

According to this video, EXP has problems that are exponentially difficult to check. But according to this video, EXP are problems that are exponentially difficult to solve. It would make sense to ...
-2
votes
1answer
42 views

Complexity and number of bits of square root number

Let an integer a, and b is the number of bits a. 1) If I have a number ...
-1
votes
1answer
37 views

Time complexity for Breadth-First search

I would like to know why the average number of nodes at level d in BFS in a search tree is $\frac{1+b^d}{2}$ as given in this lecture(p.15)?(Here b is the branching factor of the tree and d is the ...
1
vote
0answers
18 views

Wald's equation for dependent decrements

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set ...
3
votes
1answer
42 views

Linearity of Expectation

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set ...
0
votes
2answers
46 views

Generally, does the time it takes to compute (n mod m) depend on the size of n?

Example: Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits. Would the speed of the computation a mod m vary greatly from b mod m because of ...
3
votes
6answers
786 views

Is there a meaningful difference between O(1) and O(\log n)?

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
2
votes
1answer
35 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
3
votes
1answer
60 views

Why does merging two sorted arrays take 2N - 1 comparisons?

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons Prove that merging two sorted arrays of N items requires at least 2N-1 ...
0
votes
1answer
36 views

Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems ...
0
votes
0answers
29 views

Time complexity of nested for loop function involving mod to filter out the execution [duplicate]

I have to find the time complexity of the following program: ...
-2
votes
1answer
74 views

What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]

I am looking for the time complexity of the following nested loops, where the inner loop is shrinking. ...
0
votes
1answer
28 views

Runtime analysis with recursion factor

I have this code: if n is even { for i=1....n for j=1...i print j return 8*foo(n/2) } Asking to calculate the running time $T (n)$. I thought at first ...
3
votes
1answer
44 views

Recurrence: space complexity to Tournament Method

Tournament method have this structure to found min and max (function getMinMax): ...
0
votes
1answer
37 views

Space complexity of Horner's method

Following is the excerpt from wiki If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately $2n$ times the number of ...
3
votes
2answers
91 views

Why do we use big O rather than $\Omega$ when discussing best case runtime?

When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ ...
0
votes
0answers
43 views

Calculating Big-O

I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine) $ The ...