Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
804
questions
0
votes
1answer
24 views
In Big-O notation, what does it mean for T(n) to be upper bounded by something
I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? ...
2
votes
1answer
46 views
Worst case runtime for binary search
The run time of binary search is O(log(n)).
log(8) = 3
It takes 3 comparisons to decide if an array of 8 elements contains a given element.
It takes 4 comparisons in the example below.
python2.7
<...
3
votes
1answer
35 views
Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?
So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
0
votes
1answer
22 views
runtime to a BFS flood-fill with multiple centres?
If we have a flood fill algorithm which, given a number of centres reprenting pixels on an image, runs a BFS flood-fill on them, checking the pixels 4 neighbours, changing their colours and adding ...
0
votes
1answer
34 views
Upper bound for runtime complexity of LOOP programs
Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions.
Furthermore primitve recursive functions can (as far as I ...
5
votes
0answers
121 views
Time Complexity for Nearest Neighbor Searches in kd-trees
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of ...
0
votes
0answers
29 views
sequence of insert and delete operation in (2,3)-tree
I need help by understanding a theorem and its proof from a script. It says "There is a sequence of $n$ insert and delete operations in a (2,3)-tree that require $\Omega ($n log n$)$ many split and ...
0
votes
1answer
17 views
Determining whether a change in an memoized algorithm will improve the performance
I have an algorithm that constructs an optimal binary tree using dynamic programming. After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is ...
1
vote
1answer
36 views
Is log(n) equivalent to (log(n))^x for big-O analysis?
My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis.
ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$
From the ...
0
votes
1answer
52 views
Time Complexity of the below code? [duplicate]
here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part.
What is the time complexity ...
1
vote
3answers
57 views
How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?
following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity.
I tried to derive it on paper.
Let T(n) =...
2
votes
1answer
38 views
Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)
I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author ...
1
vote
1answer
25 views
Given a set of sets, find the magnitude (number of elements) of the smallest set containing at least one element from each set
I know that the hitting problem is NP hard, but is it possible to find the magnitude of the smallest set? Also, provide the runtime.
0
votes
1answer
22 views
Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))
I am learning about algorithmic complexities and I read that if f(n) and g(n) are asymptotically positive functions and if $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds.
I ...
0
votes
0answers
34 views
time complexity of 2 sum problem using binary search
this is a popular searching problem and the question is :
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The ...
1
vote
1answer
39 views
Do problems that have unary encodings automatically become unary languages?
This problem has confused me a lot, can any of you help me out.
Thank you.
0
votes
0answers
26 views
proving long asymptotic bounds
I'm trying to find ways this simplify this formula and assuming numbers but that doesn't seem to help, the question is asking to prove or disprove:
$$ 3n(\log_{}n)^2 + 4n = \Omega (2n^2 \log_{}n +1) $...
0
votes
1answer
39 views
Why does this triple loop code have a running time of 1.5lnN * N^2
Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term ...
2
votes
1answer
30 views
number of comparisons in searching algorithms
i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these.
For linear search :
...
0
votes
1answer
40 views
Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$
I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?
Algorithm A
...
1
vote
3answers
79 views
Derive a while loop runs in $\Theta( \sqrt{n} )$
I know for a fact that algorithm A runs in $\Theta(\sqrt{n})$, but how does one derive that fact?
Algorithm A
i = 0
s = 0
while s <= n:
s += i
i += 1
...
1
vote
1answer
64 views
Running time of algorithm (effect of j*j in for loops) - Theta Runtime
In Theta notation what are the running times of these algorithms?
Algorithm 1
for i=1..n
j=1
while j*j <= i:
j = j + 1
Since the outer loop ...
1
vote
1answer
106 views
Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?
I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail?
If we divide into ...
0
votes
3answers
157 views
How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$
I understand that essentially we have to prove that
$$c_1(n^2\log n)\le
(56n^2+106n+48)(\log(264n^2+200))
\le c_2(n^2\log n)\,.$$
I am confused on how to simplify this further? And ...
1
vote
1answer
28 views
Runtime-Analysis for single loop incremented by a factor of 3
So, I'm trying to understand how to get the run time of this loop:
for(int i = 1; i < n*n*n; i*=3) {...}
So, far I know:
loop starts at 1
finishes when $i &...
1
vote
1answer
24 views
Maximum-cardinality matching in unbalanced bipartite graphs
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So ...
0
votes
0answers
23 views
Time complexity of simple function related to bits
I am wondering about correct answer to this task from a yesterday's test:
A function Pow which calculates $y = a^k$ is given, where $k$ is an
integer of length ...
0
votes
1answer
47 views
What time complexity is more significant? [closed]
A certain algorithm executes $n$ operations of three types: insert, delete, and find.
We know that $n/10$ of the operations are inserts, and the rest are deletes and finds.
You are given two ...
0
votes
1answer
25 views
Complexity Class of an Algorithm with two Inputs
Consider a problem with two inputs like (P,L) and |P|=n and L is some positive integer. If my algorithm had a complexity of O(n^L), would that still be polynomial? Or is it exponential? I'm not sure ...
0
votes
0answers
42 views
Proof of the average case of the Heap Sort algorithm
Consider the following python implementation of the Heap Sort algorithm:
...
0
votes
0answers
26 views
How many inputs N can be placed into a function ln to get a certain amount of time?
it's "gardening" time, which means studying algorithms. A question in Intro to Algorithms 3rd Edition is a chart asking me how many of N inputs can be placed into a function to get a certain amount of ...
2
votes
1answer
59 views
runtime of 2 dependent nested for loops [duplicate]
for (i=1; i<=n ;i=i*2){
for (j=1; j<=i ;j++){
basic_step;
}
}
Regarding the above nested loops, I can't seem to understand why is the following ...
0
votes
3answers
64 views
Is there a unit of measurement that can express code execution speed in absolute terms?
I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
0
votes
2answers
45 views
Karatsuba Multiplication Rule in dividing a Number in two parts
In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example:
x= 1234
y= 2456
Then a = 12, b = 34, c = 24 , d = 56
What if ...
1
vote
1answer
64 views
How to find an algorithm's complexity from actual running times
I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...
2
votes
1answer
38 views
Average Case Running Time of Quicksort Algorithm
From this website, it states that the average case of Quicksort algorithm is
T(n) = T(n/9) + T(9n/10) + θ(n)
Im a bit confused. Is it supposed to be ?
...
1
vote
1answer
45 views
Recursion Time Complexity (Half n' Half)
This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:
Input: string $s = s_1,\ldots,s_n$, integer $k$
Go over all symbols $s_1,\ldots,s_n$, one by one
...
0
votes
2answers
83 views
How to find i-th root of n whose remainder is the smallest?
Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively ...
2
votes
1answer
23 views
Analysis of straight insertion
I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot ...
0
votes
0answers
22 views
How to apply AC-3(Arc-consistency 3) algorithm in N-Queen problem?
I am building N-Queen Solver with java.
I confused with AC-3 algorithm.
I heard that AC-3 can be applied with backtracking algorithm before processing and during the search.The latter is called MAC-3 ...
0
votes
0answers
30 views
Choosing algorithms and/or data structures at runtime based on input characteristics
I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
-3
votes
2answers
135 views
BigO time complexity of 3 nested for loops
I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$
I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$
...
0
votes
0answers
9 views
Shortcuts/Patterns for being able to calculate the running time of a loop/algorithm? [duplicate]
This is my first question here. I, like many people, suffer from the lack of the ability to be able to determine the running time of algorithms just by looking at them. I've picked up on a few ...
0
votes
0answers
30 views
Big oh notation run time [duplicate]
I have this Question , I want the answer and show me how to solve it Please :
Analyze the running time of the following algorithm using Big-Oh notation
...
2
votes
1answer
39 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
15 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
59 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
120 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
75 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
41 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^{...
