Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
5
votes
1answer
44 views
How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?
int n;
cin >> n;
int sum = 0;
for (int i = 1; sum <= n; i++) {
sum += i;
}
If I assumed that $N = 100$, the loop will run $13$ steps, ...
-1
votes
1answer
31 views
Mergable heap with no key knowledge cannot EXTRACT-MIN in $o(\log n)$ amortized time
We are looking into Fibonacci heaps in class at the moment, but I am stuck with this problem. Let $H$ be a mergable heap structure, by which is meant a data structure, where each element has a key, ...
1
vote
0answers
52 views
How to find big-O for an in-place perfect shuffle algorithm
I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
0
votes
2answers
20 views
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
If I have a recursive function like this for example (This is just an ...
1
vote
2answers
28 views
Running time complexity of finding maximal power of divisor that divides natural number
Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of ...
0
votes
1answer
25 views
algorithm analysis - complex dependant nested loop
First of all, I know there are many questions like this on the site. But I think this case is a bit different.
Consider the following code:
...
0
votes
1answer
14 views
Optimal scalability of a distributed algorithm
What's the optimal scalability of some algorithm when I implement it in a distributed manner?
Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes....
4
votes
0answers
30 views
Highest stack of rectangles
Suppose we have a set of $n$ dimensional rectangles $R = \{(x_{i,1}, \ldots, x_{i,n}), i \in 1 \ldots k\}$. We want to create the highest stack in say the first dimension such that each side of the ...
0
votes
0answers
35 views
Reccurent runtime
If $T(n) = T\left(\frac{n}{2}\right) + 5$ (binary search), then the runtime in Big-O notation is $O(\log(n))$.
If $T(n) = T\left(\frac{n}{2}\right) + 0$, then is it correct to say that the the ...
2
votes
1answer
40 views
Euclidean algorithm and well define ness on the underlying set
Euclidean algorithm is given below:
gcd($a$,$b$):
if $a=0$, return $b$
otherwise, return gcd($b \bmod a$, $a$)
Let us first argue that the algorithm terminates. The reason ...
0
votes
0answers
34 views
Finding runtime of a recurrence relation with a fractional power
Consider the following algorithm and find the tightest Big-$O$:
Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$.
If my runtime is $T(n)$, I have:
Lines 1 ...
0
votes
3answers
59 views
What is the asymptotic complexity of the following code snippet?
for (i = 2; i < n; i = i * i) {
for (j = 1; j < i / 2; j = j + 1) {
sum = sum + 1;
}
}
I know that the outer loop can run for a maximum of $n^2$ ...
1
vote
1answer
33 views
Heap operating in time $\Gamma^{-1}(n)^2$
I have a priority queue implementation which I claim has the following worst case asymptotic run-times for the given operations:
PEEK_MIN …………………………… O(1)
POP_MIN…………………………… O( (INVERSE_Γ(n)) ^2).
...
4
votes
2answers
62 views
Run-time of Hungarian algorithm - matrix formulation
There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a ...
2
votes
1answer
49 views
Djikstra algorithm analysis
My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that?
Dijkstra algorithm pseudocode:
...
-1
votes
1answer
50 views
What would be the big-o time complexity of this scenario? [duplicate]
I am wondering what the time complexity of a for loop that increments the control variable, but also multiplies it inside the loop. For example
...
1
vote
2answers
52 views
Running Time of Sorting Algorithm
Determine the asymptotic running time of the sorting algorithm maxSort.
Algorithm maxSort(A)
Input: An integer array A
Output: Array A sorted in non-decreasing order
...
2
votes
1answer
61 views
Running Time for Finding Maximum
Consider the algorithm findMax that finds the maximum entry in an integer array.
Algorithm findMax($A$)
Input: An integer array $A$
Output: The maximum entry of $A$
...
2
votes
1answer
39 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
50 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
2answers
86 views
Time complexity of Dijkstra's algorithm for sparse graph
I'm not sure I understand the answer to this question:
Question 9.
What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, ...
0
votes
1answer
42 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 ...
0
votes
1answer
62 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
4answers
390 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
80 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
57 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
92 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
36 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
84 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
28 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
24 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
28 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
117 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:
...
-1
votes
1answer
121 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
24 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
17 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
511 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
50 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
43 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
30 views
1
vote
0answers
43 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
54 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
24 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
148 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)$.
...
