Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
2answers
54 views

Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

I am working on proving the time complexity for the following problem, but believe I am stuck: $$T(n) = 2T(n/3 + 1) + n$$ I have checked out this link here on time complexity on cs.stackexchange ...
0
votes
0answers
36 views

Misunderstand a algorithm

I fail to understand a algorithm, basically the matrix multiplication portion. I can explain the unknown terms. At line no: 4 j will be 1,2,3,....,15. When ever new object is observed a value ...
1
vote
0answers
34 views

Linear Time Selection Algorithm

In the linear time selection algorithm which finds the ith smallest element in O(n) time our first step is to divide our unordered set into subsets of 5. Why is the size of the subsets chosen to be 5 ...
3
votes
0answers
80 views

Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$

We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$. The obvious naive way ...
1
vote
0answers
25 views

Calculating the complexity of an algorithm exercises

I am really bad at calculating correctly the complexity of a given algorithm. I would like to know if there is some book or online resources where I can find many exercises that ask to calculate the ...
1
vote
1answer
55 views

Can we do 4-sum algorithm in O(n^2)?

this is related to the following question: Generalised 3SUM (k-SUM) problem? Without loss of generality, let's only consider even $k$, or just $k=4$. My question is, after summing all pairs of ...
0
votes
3answers
63 views

Big O notation for Sorting Algorithm

I am interested to know whether the time complexity of following algorithm is $O(n^2)$ or $O(n\log n)$. Here is the implementation: ...
1
vote
0answers
11 views

Given a simple graph G, what's the quickest known way to sample one of it's spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle. We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
1
vote
0answers
39 views

Measure the degree of differences between web pages

I'd like to measure how different two HTML files are from each other. I refer to the following scenario: User A visits a website, let's call the website example.com User A shares the website with ...
-1
votes
1answer
31 views

Finding recurrence equation for a variant of insertion sort [closed]

I have a variant of Insertion sort (recursive version) that we call split insertion sort because there are two kinds of input. The input array has both numbers and alphabets, hence we have to sort ...
3
votes
1answer
51 views

Is binary-search really required in Chan's convex hull algorithm?

I have a little doubt about Chan's algorithm. From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q_i$. The goal of the ...
2
votes
1answer
57 views

Average-case complexity of linear search where half of the elements in the array are duplicates

I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows: A(n) = $\frac{n + 1}{2}$ However, I am having trouble coming up with the Average ...
2
votes
1answer
36 views

Merging $k$ sorted lists in $O(n\log k)$ time

This question is based on a solution of Laura Toma to a question from CLRS (#6 on the sheet). Question: Give an $O(n\lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is ...
2
votes
1answer
43 views

Median of medians: bound on pivot position

If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at ...
-1
votes
2answers
74 views

Divide-and-conquer: Determining the top two candidates and whether these two candidates received more than n/2 votes

Suppose that each person in a group of n people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each ...
0
votes
1answer
30 views

Relations between different time complexities of an algorithm

If I have an algorithm A that, in the worst case, has a lower bound of $Ω(n\log n)$ and an upper bound of $O(n²)$, how can I go about determining possible time complexities for best and average cases? ...
2
votes
2answers
62 views

Proving Postorder Traversal's Time Complexity

I am looking at the following algorithm for performing a Postorder Traversal of a binary tree ...
0
votes
1answer
37 views

Is there a fast algorithm for computing the rolling mode of an array of integers?

I was wondering if there exists an efficient algorithm for calculating the "rolling mode of an array of integers. By rolling mode I mean that we have an array of integers of size $n$ and a sliding ...
0
votes
0answers
29 views

Prove lower bound of searching algorithm on Young Tableau

I want to prove the search of an element in a Young tableau of size $n\times n$ is $\Omega(n)$, but I do not have any clue. Any help is appreciated!
1
vote
1answer
28 views

Theta bound of the following function [duplicate]

Suppose the function $f(n)$ is defined as the number of $\ast$ printed in the following code ...
2
votes
1answer
59 views

What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent ...
2
votes
1answer
48 views

Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks

Lets just say I have two lists of the running time of tasks A and B. Formally, I would have: A = {a_1, a_2, a_3 ... a_n} B = {b_1, b_2, b_3 ... b_n} I can only ...
3
votes
2answers
36 views

Possibility to prove that a function in big-theta is in big-O and little-o

I understand that many similar questions of this sort have been asked, but in this case, the solution does not appear to be provable - or is it? Question: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))...
0
votes
1answer
32 views

Exponential nested Loop Big O complexity calculation [duplicate]

Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this ...
1
vote
1answer
38 views

quicksort recurrence relation

In Concrete Mathematics Textbook by Donald Knuth and Oren Patashnik , ch.2 Sum ,sec2.2 He wrote: The average number of comparison steps made by quicksort when it's applied to $n$ items in random ...
0
votes
2answers
41 views

1D Peak-finding problem, how to derive the formula?

I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem. About the problem Basically, there's an array of numbers and we want ...
0
votes
0answers
30 views

Hard Big O complexity for 3 loops [duplicate]

So this is a tricky one, i try to calculate Big O complexity for this code but I always fail.... I tried to nest SUM's or to get the number of steps for each case like: i=1 j=1 k=1 (1 step) i=2 j=1,...
1
vote
2answers
42 views

Fast algorithms that work on some large percentage of possible inputs

I've been wondering if research of these algorithms exists. An example, let's say I'm fine with $p$% of possible inputs of size $n$ to be unsorted. Is there an algorithm that would allow me to sort $n$...
1
vote
2answers
57 views

How to determine seed collision probability in a PRNG?

I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds ...
-1
votes
1answer
54 views

Do we always get the same set of edges after running Kruskal's algorithm on a single graph?

I think it should be false because there may be more than one edge with the same weight.
1
vote
1answer
44 views

Dijkstra Partitioning Algorithm : Special Case

I have been exploring Dikstra partitioning Algorithm. Below are my given: R = Red W = White B = Blue I have this unpartitioned array. ...
2
votes
1answer
236 views

Why is this n^2 growth?

I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading: "... performs of the order of $n^2$ steps on a sequence of length $n$....
0
votes
1answer
20 views

What is the output of below algorithms on a disconnected Graph?

If I apply Dijkstra's ,BFS or Bellman-ford algorithm on a disconnected Graph then will the output be a tree or a disconnected Graph only because even if we have a disconnected Graph and we run ...
1
vote
0answers
30 views

distinguishing two biased coins

I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many ...
0
votes
0answers
24 views

Extended stars and bars approach using dynamic programming

If we have an equation with N variables of the form x1 + x2 + x3 +...+ xN with sum S, and upper and lower bounds for each of the N variables, is it possible to find the number of integer solutions (...
-1
votes
1answer
28 views

Book example Profit maximization understanding [closed]

This may not be the right place to ask this kind of question and it also sound a bit stupid, but please help me understand better. I am not able to to see why on page 192 "which imposes another ...
3
votes
2answers
312 views

Time Complexity to find height of a BST

Below is a question I was asked in an Interview What is the best case time complexity to find the height of a Binary Search Tree? I answered it explaining using the below algorithm $\mathrm{...
4
votes
1answer
56 views

How do non-deterministic algorithms work on current machines?

I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia ...
2
votes
0answers
33 views

Analysis expected depth of a binary search tree given random values?

I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
1
vote
1answer
38 views

T(n) = aT(n/b)+f(n), I don't understand the difference between a and b

I was analyzing the time complexity for recursive algorithms like merge sort, but when I came across that recurrence, [I think that equation is called a recurrence right?] I couldn't differentiate ...
1
vote
2answers
64 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
1
vote
1answer
38 views

Why do we consider the order of growth when analyzing algorithms? [duplicate]

Seriously why do we consider how the computation time time increase with the number of inputs as a measure of performance when we can easily measure such as program execution time,power consumption,...
3
votes
1answer
55 views

Does the space complexity of a recursive algorithm depend on the total no of recursive calls?

I am confused whether space complexity of a recursive algorithm depends on the total number of recursive calls or not. Say I have an algorithm which has exponential function calls, but stack size is ...
1
vote
1answer
44 views

Why do we discard the constant 1 in proving that $2^{n+1} = O(2^n)$

In this post someone said: $n + 1$ is approximately equal to 1 for $2^{n+1} = O(2^n)$. I don't understand this point. For example, in this example: $$ n + 1 \leq c \cdot n $$ for some $c$ and ...
0
votes
0answers
45 views

How to prove n^2 != o(n^2)? [duplicate]

I think I barely understand the usefulness of asymptotic notations. And I came across small o and I want to prove that statement is true. But I have no idea how to start. Those are 2 extra problems ...
0
votes
0answers
21 views

Hessian in reinforcement learning

The Hessian of multi-layered network exhibits known behaviour at critical points as shown in [1]. The tools of random matrix theory allow [2] to deduce the asymptotic distribution of the eigenvalues ...
0
votes
1answer
81 views

Time complexity of kruskal using array data structure

I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps: Sort the edges as ...
1
vote
1answer
33 views

Understanding Binary Search for Kth Smallest element in an Array

The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 ...
1
vote
2answers
430 views

What is the difference between Big O and Theta notation in terms of inputs?

In Coreman , it's written : The $O(n^2)$ bound on worst-case running time of insertion sort also applies to its running time on every input. The $\Theta(n^2)$ bound on the worst-case running time ...
2
votes
1answer
60 views

What is the current state of the art in solving the halting problem? [closed]

Yes, I know it's uncomputable in the general case. What I want to know is what special cases have been solved, and if there is work ongoing on finding or developing more of them. To be a little more ...