Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
1
vote
1answer
7 views
The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm
I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why.
Here ...
3
votes
0answers
13 views
Power of 2 assumption in Divide and conquer [duplicate]
Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the ...
0
votes
1answer
44 views
Complexity of finding a majority element
I was given a question that is stated that;
Suppose you’re consulting for a bank that’s concerned about fraud
detection, and they come to you with the following problem. They have
a collection ...
0
votes
1answer
20 views
My code works, But how do I make this code run in a deterministic time?
The Problem:
Given 3 inputs Bounce, Ball drop height, and ball view height.
How do I calculate the number of times the observer can see the ball pass.
So my code gives correct output, but it takes ...
2
votes
0answers
19 views
Tail recursion can't work with dynamic programming programs
I am doing some exercises on dynamic programming in order to get familar with this concept.
I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
0
votes
0answers
21 views
between hoare and lomunto quicksort which give better cache performance?
between hoare and lomunto quicksort which give better cache performance ?
we know that in hoare quicksort we move the pointer i,j in different direction but in lomunto quicksort we move i,j in same ...
2
votes
1answer
23 views
minimum number of nodes that traverse all the graph
In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
-4
votes
0answers
15 views
Complexity of CYK algorithm [on hold]
What is the Big O complexity of the CYK ( Cocke–Younger–Kasami ) algorithm as a function of the size of grammar G?
2
votes
1answer
19 views
0
votes
0answers
24 views
If you have two recursive calls in a function and one terminates before the second how do you calculate the time complexity? [duplicate]
Suppose you have a function which calls to itself twice. So both go down recusively until they reach some condition. But one of them will go less times than the other. For example one would call ...
1
vote
0answers
30 views
Upper bound on the average-case runtime of shell sort
I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $\Omega(N \log N)$ in average cases.
I want to know the upper bound complexity in average cases, so I write
...
-1
votes
0answers
14 views
Collect stamps, algorithm
Suppose you have a box full of stamps. There are $a$ stamps in the box. You want to get the $b$ oldest stamps from the box. Whereby $a$ is much bigger than $b$. What would be the best algorithm (worst-...
1
vote
0answers
19 views
Complexity of bisection method for finding an interval
Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]...
1
vote
1answer
22 views
Running time based on smallest subtree
I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More ...
1
vote
1answer
42 views
Finding the Kth largest element can be optimized to O(n) only if k is a constant?
There's a famous question posted on this site which asks about finding the $k$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $O(n)$.
...
1
vote
2answers
50 views
What is the real reason that Bubble Sort runs at O(n) in best case?
In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only ...
4
votes
2answers
80 views
Is “super-exponential” a precise definition of algorithmic complexity?
I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.
For instance, if an algorithm runs for $nC(n-1)$...
1
vote
1answer
38 views
Adding two running time from a function
I have a method Func() that has two inner methods Func1() and Func2().
...
1
vote
1answer
28 views
Summation Properties of Big Omega
What are the properties of summation with Big Omega? I have been looking online but cannot find any sources on summation with Big Omega, only for Big Oh. For example, my main inquiry is if this ...
0
votes
1answer
10 views
A hangman variation: determining a string by guessing substrings contained in it
I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I ...
0
votes
1answer
19 views
Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm
For the following algorithm,
$X\leftarrow \{(i, n - i) | i = 1, ..., n- 1\}$
while $\max_{(a, b)\in X}b > 0$ do
$\quad X \leftarrow \{(|a - b|, \min\{a, b\})|(a, b) \in X\}$
...
1
vote
2answers
49 views
Is the runtime of binary search big omega of logarithm of n?
My question is that can we say that runtime of the binary search is $\Omega(\log n)$?
I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
0
votes
2answers
46 views
Running time of median of 3 partioning
I am hoping someone can break something down for me in a way I can digest.
I am trying to understand the running time for the median of three partitioning.
What is the goal of median of three ...
0
votes
0answers
27 views
Big-O of a recursive function [duplicate]
just wondering, what's the big o of this function,
let say the initial value of the parameters is as following:
...
0
votes
0answers
14 views
Can we update a cut-block tree in linear-time?
Every graph $G$ admits a cut-block-forest decomposition. This is a forest $F$ where each node corresponds to a maximal 2-connected component (called block) in $G$ and two nodes are adjacent in $F$ if ...
1
vote
1answer
45 views
Run-time of Sorting Algorithm
Problem
Consider the pseudocode for the sort algorithm below, which takes as input an unsorted array $A$ of $n$ integers with no duplicates.
...
2
votes
2answers
75 views
Logarithmic run time for calculating prime numbers?
Here's the function I'm currently analyzing. I know it's not the most optimal but I'm not understanding the $\theta()$ of this algorithm. I've been told that it's not actually $\theta(n)$ but instead ...
1
vote
1answer
68 views
How many rotations after AVL insertion and deletion
Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?
How many rotations, does deletion from AVL require?
I've searched for these two questions with no luck so far.
0
votes
1answer
74 views
what is the time complexity for binary division by repeated subtraction?
The divisor and dividend are of length n and m bits respectively.
According to Wikipedia article,
https://en.wikipedia.org/wiki/Output-sensitive_algorithm
division by substraction is an output ...
2
votes
1answer
34 views
Selection Sort Analysis
I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers):
...
1
vote
0answers
18 views
How does the browser
I wondering how the browser's JS runtime implements these methods. I looked on the web and could not find any documentation.
How does something like the V8 runtime actually work to implement these ...
1
vote
1answer
19 views
Should I keep a relevant constant in the Time Complexity?
I designed an algorithm, and the Time Analysis provided next time complexity:
$\mathcal{O}(2^p \cdot (\frac{t}{2}/2^p) \cdot \frac{n}{4})$
what must be simplified to:
$\mathcal{O}(2^p \cdot \frac{...
2
votes
2answers
69 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
...
-1
votes
2answers
46 views
What is the Big-O runtime of this algorithm? [duplicate]
Can anyone explain why the runtime of this is in O(N^3)?
Additionally, what would the run-time be in Big-OH if the else statement was removed.
...
1
vote
0answers
27 views
Calculating the complexity of an algorithm exercises [duplicate]
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
2answers
53 views
What does ∈ mean in the exponent?
I'm having troubles understanding the following proof:
$$
\begin{align*}
&\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\
&\...
-1
votes
1answer
71 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 ...
1
vote
3answers
62 views
Optimizing coin splitting - Is this algorithm as fast as I think?
In a recent exam, I've been asked to solve the following problem:
The problem
Two players play the following game: Given a sequence of coin values
$v_1,\ldots,v_n (n \vert 2)$ the players ...
1
vote
1answer
29 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
132 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 ...
1
vote
1answer
63 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 ...
-1
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,...
2
votes
1answer
35 views
Why does parallelising slow down this simple problem against looping through all the data?
I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn ...
0
votes
0answers
36 views
What is the time complexity of MATLAB's ode solvers?
Say I have a system that is $n$ differential equations that are all coupled together, over a time interval $[a,b]$ with timestep $t$. Is there a straightforward time complexity for MATLAB's built in ...
1
vote
0answers
22 views
Randomized meldable heap - meld is oversimplified?
On both Wikipedia and the paper it was introduced the randomized meldable heap uses the following procedure to meld two heaps:
...
1
vote
2answers
68 views
1
vote
1answer
66 views
Time complexity of transforming one string to another
Here is the problem:
Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production ...
3
votes
1answer
48 views
Why is the graph inside Graham Scan always planar
One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's ...
0
votes
3answers
150 views
In place and Out place sorting meaning?
What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.
2
votes
1answer
65 views
Complexity of polynomial interpolation
Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
