Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
0
votes
0answers
24 views
Is data serialization efficient? For example, how do I understand the runtime of pickle in Python?
I have two pandas dataframe
data1 = pd.read_csv("1.csv")
data2 = pd.read_csv("2.csv")
And then I concatenate it.
...
1
vote
0answers
10 views
Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial
This question is about section 2.3 of Wilf's ``Algorithms and Complexity''
https://www.math.upenn.edu/~wilf/AlgoComp.pdf
in which he analyses the complexity of a recursive computation of the ...
0
votes
0answers
12 views
Growth rate and runtime [duplicate]
Sorry if this maybe a dumb question, just a little confused
But with Big-Oh notation, does it measure the runtime or growth rate of an algo? or both?
0
votes
2answers
24 views
Karp-Rabin - what is the input for the worst case time complexity?
I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet:
String "AAAAAAAA" ...
2
votes
1answer
34 views
Running time for Breadth-First-Search vs Depth-First-Search
Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$.
I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS.
...
1
vote
0answers
48 views
Convex hull partition of a set of points
Given a set $S$ of $n$ points in $\mathbb R^2$, denote by $\mathrm{convb}(S)$ the boundary of the convex hull of $S$. Let
\begin{align*}
S_1 &= \mathrm{convb}(S)\\
S_{i+1} &= \mathrm{convb}\...
1
vote
2answers
37 views
Running time correct with Omega?
I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$.
Because:
I know $\log(2^n) = n$.
By that I would guess the same goes for $\log(n^{...
0
votes
1answer
29 views
Big O of runtime operation n-m+1 [duplicate]
I have a loop that runs n-m+1 times where
m = len(list_m)
n = len(list_n)
for i in range(n-m+1):
Is this time complexity O(n-m+1)?
0
votes
0answers
18 views
Run time of pseudo code in big theta notation [duplicate]
I am looking for the run time of the following pseudo code.
...
0
votes
1answer
33 views
Worst Case Scenario for Quicksort algorithm with pivot element n/2
What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element?
I know that if I choose the left or rightmost element as pivot ,the ...
1
vote
3answers
79 views
What should I call algorithms with non-linear non-constant time?
I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g ...
2
votes
2answers
368 views
All superlinear runtime algorithms are asymptotically equivalent to convex function?
Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?
All the examples that I could think of satisfy the above ...
2
votes
2answers
48 views
Is purely functional programming in some situations less efficient than imperative programming?
I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
0
votes
0answers
15 views
Why does the knapsack dynamic programming solution has runtime of O(nW)? [duplicate]
Can you please help me analyse the runtime of the knapsack dynamic programming (which i have seen somewhere is O(nW))?
This is the algorithm i an using:
Define M[i,s] to be the maximum value that ...
1
vote
1answer
44 views
Big Oh Time Complexity Involving 'for i in range(n)' [closed]
Given the code below and the comment analysis:
...
3
votes
1answer
488 views
Complexity of many constant time steps with occasional logarithmic steps
I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant.
Is it possible for this task to ever take ...
0
votes
2answers
47 views
Does my solution converge to O(N) for worst-case time complexity?
Forgive me if this should be in StackOverflow or Mathematics instead!
I was given the following question at an interview:
...
1
vote
0answers
25 views
Time and space complexity of a recursive problem (code included)
I am having trouble finding out the time and space complexity for this recursive solution. I have to create a list of words in order of word length. Each word, must be one character insertion off from ...
3
votes
0answers
44 views
Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm
I have a graph algorithm that runs in:
$$ T(n, m) = \begin{cases}
c_1 & n \leq 2 \lor m = 1\\
T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\
T(n - i,\ m) + T(i, m) + ...
1
vote
1answer
44 views
Are all hypothetical machine models for calculating runing time of an alogrithm same?
Im learning about time complexity analysis, and cant seem to figure out why do we consider a hypothetical machine that takes 1 unit of time for arithemitic and logical instructions and 1 unit of time ...
5
votes
1answer
66 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
39 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
55 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
31 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
34 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
19 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
40 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
38 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 ...
1
vote
1answer
43 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
36 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
63 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
40 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
78 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
58 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
58 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
64 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
60 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
54 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
274 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
102 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
2answers
89 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
402 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
82 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
60 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
203 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'.
...
