Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
2
votes
1answer
30 views
Complexity of brute force primality test in the number of digits
I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime ...
3
votes
1answer
45 views
Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?
I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following:
Let $F(x)$ be given as a product
$F(x) = \prod_{...
1
vote
0answers
36 views
A look at an exact smallest grammar algorithm. How do we compute running time big-O?
A smallest grammar of a string $s$ over an alphabet $\Sigma$ is a smallest CFG $G$ such that $L(G) = \{s\}$, where size is the total number of symbols occuring on the right sides of production rules ...
0
votes
1answer
27 views
Why is a heap better than a linked list for implementation of a priority queue?
Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.
Why is it better to have log-n for both than n for one and constant ...
0
votes
0answers
15 views
Runtime explanation of this function [duplicate]
I am trying to understand the runtime complexity of the below code in terms of n.
I know that it is $Θ(n^{4/3})$, but I don't get why.
I thought the outer loop runs $log(n)$ times, the second one ...
-2
votes
0answers
19 views
0
votes
1answer
54 views
Is there a useful algorithm with a decreasing asymptotic time?
Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the ...
0
votes
1answer
22 views
Why $xx^TM$ requires $O(dk)$ operations?
Suppose $x \in \mathbb{R}^d$ and $M \in \mathbb{R}^{d \times k}$.
Why $xx^TM$ requires $O(dk)$ operations?
2
votes
3answers
333 views
Why aren't primality tests easily linear in time complexity?
Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear.
I assume it's not linear only if we compare the ...
0
votes
1answer
38 views
How do you find set of keywords present in set of words in linear time or log time?
I am trying to optimize a program, where I need to know whether a given set of keywords present in the set of words. I believe using the dictionary is the only way to optimize it. Any other technique ...
1
vote
3answers
76 views
Show that the following algorithm takes $O(n)$ time
You are given a linked list of size $n$.
An element can be accessed from the start of the list or the end of the list. The cost to access any location is $\min(i,n-i)$, if the location being accessed ...
5
votes
1answer
56 views
Least number of guesses needed to determine all unknown subsets of a set
Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and ...
0
votes
1answer
37 views
Create a binary search tree from a sorted array: Space complexity reasoning
Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'.
...
0
votes
1answer
28 views
What will be big O complexity for this loop? [duplicate]
I am not able to understand time complexity of this for loop.
While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity?
...
0
votes
1answer
34 views
Big O analysis for problem where number of items searched is unknown
Consider this problem: you are searching an array of elements and are comparing the square of the current element to some number K. Essentially, you are looking to see if the square root of K is in ...
0
votes
0answers
15 views
Merge Sort Recurrence analysis for list of strings [duplicate]
I saw this question and tried to find out what the time complexity was:
Using the recurrence relation for Merge Sort:
$$T(n)\; =\; merge\_time\; +\; 2T(n/2)$$
Here, since we have a list of strings, ...
2
votes
1answer
80 views
How to find efficiently the minimum modification to avoid close consecutive numbers?
I have an array of sorted numbers:
arr = [-0.1, 0.0, 0.5, 0.8, 1.2]
I want the difference (dist below) between consecutive ...
0
votes
0answers
22 views
Worst case lower bound of binary search
For the question below, it is asking to prove the lower bound on the worst case is log(n). I have no problem proving this and the solution makes 100% sense to me. However, there is a comment at the ...
0
votes
1answer
19 views
Time complexity dependent on magnitude of input [duplicate]
I'm trying to analyze an algorithm that looks like this:
def foo(L):
for n in L:
for x in range(n):
...
What would be its time complexity?...
1
vote
1answer
23 views
Find the efficiency class
I have to find the efficiency class of this algorithm
b = 3
a = 4
for i = 4 to n^2
if (i mod 2 == 0)
a = a+2
else
b = b*3
end for
I ...
0
votes
1answer
60 views
Big-O notation for nested loops that might skip iterations
When you have an algorithm that may skip a lot of iterations due to a hash table lookup, do you still count the iterations that are exited immediately?
Hypothetical example:
...
0
votes
0answers
14 views
time complexity of recursive algorithm with loop [duplicate]
For approximating a recursive algorithms time complexity i found some great techniques e.g. here. But i'm not sure how one to get the time complexity of a recursive algorithm with a loop in it.
For ...
-1
votes
1answer
56 views
Finding time complexity when while loop included [duplicate]
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, ...
1
vote
1answer
19 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
15 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
119 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
27 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
24 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 ...
2
votes
1answer
36 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 ...
2
votes
1answer
27 views
-1
votes
0answers
32 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
36 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
vote
0answers
23 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
23 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
64 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
55 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
110 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
42 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 ...
1
vote
1answer
18 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
28 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
54 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
76 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
16 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
50 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
78 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
277 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
106 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
37 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 ...
