Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

Filter by
Sorted by
Tagged with
1
vote
0answers
326 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
25 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
265 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
1answer
45 views

Adding two running time from a function

I have a method Func() that has two inner methods Func1() and Func2(). ...
4
votes
2answers
17k views

How to calculate the mergesort time complexity?

Recently while reading a book (Skienna) I came across the following statement: Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of ...
1
vote
1answer
120 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
40 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
218 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 ...
3
votes
1answer
2k 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
2answers
1k 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 ...
1
vote
3answers
2k 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.
3
votes
2answers
4k views

Using software to calculate the complexity of an algorithm

I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
1
vote
1answer
76 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. ...
11
votes
2answers
2k views

Simplify complexity of n multichoose k

I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression. In my case, $k$ ...
2
votes
2answers
121 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 ...
0
votes
1answer
259 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
54 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
19 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
30 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
597 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
64 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
452 views

Help with deterministic selection algorithm

All we know what is Deterministic Selection Algorithm: Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
1
vote
0answers
29 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
59 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
357 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 ...
2
votes
3answers
83 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
32 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 ...
4
votes
1answer
2k 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 ...
2
votes
2answers
131 views

What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?

I am currently studying the paper Primes is in P and have a question regarding 5 section of this paper. Line 1 of the algorithm (on page 3) requires the following operation to be performed ...
1
vote
1answer
304 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 ...
2
votes
1answer
324 views

Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case? Even in the case of a reversely sorted list, it's not like it'll have ...
1
vote
1answer
326 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 ...
1
vote
1answer
2k views

Python: A doubt on time and space complexity on string slicing

This qns is from my school's exam paper. Context: In a game of Hangman, player tries to uncover a hidden word by guessing the letters in the word. Assume all words and letters are lowercase. The ...
0
votes
0answers
87 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 ...
3
votes
1answer
58 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
1answer
77 views

assigning running time [duplicate]

I'm trying to assign running times to loops of code to roughly get the upper asymptotic ($O$) running time. ...
1
vote
0answers
102 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
125 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
3
votes
1answer
84 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 ...
2
votes
1answer
150 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 ...
2
votes
3answers
7k views

How can I prove that a build max heap's amortized cost is $O(n)$?

Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?
4
votes
1answer
214 views

Exponential time local search heuristics for Weighted MAX-CUT-Flip

I have read multiple times [Theorem 5.15, 1][End of page 2, 2] that local search heuristics for $\textsf{Weighted Max-Cut}$ with $\textsf{Flip}$ neighbourhood takes an exponential time in some cases. ...
1
vote
2answers
2k views

What is the difference between Big O and Theta notation in terms of inputs?

In Coreman , it's written : The $O(n^2)$ bound on worst-case running time of insertion sort also applies to its running time on every input. The $\Theta(n^2)$ bound on the worst-case running time ...
1
vote
2answers
58 views

Time complexity for this simple loop

This is the code: j=2 while j<(n*n) j=j*j At first my approach was to treat this like this loop ...
32
votes
3answers
3k views

Will hardware/implementation affect the time/space complexity of algorithms?

I’m not even a CS student, so this might be a stupid question, but please bear with me... In the pre-computer era, we can only implement an array data structure with something like an array of ...
2
votes
1answer
80 views

Average Case Analysis for finding max in array with duplicated element

I've read some posts about counting the number of assignment inside code of finding the maximum value in array like this: ...
3
votes
3answers
2k views

Is there any difference between Time Complexity and Running time?

Is time complexity and running time of the program/algorithm one and the same thing? Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that ...
1
vote
1answer
153 views

Definition of an Upper Bound

The definition my professor gave us is: f(n) is O(g(n) for constant c > 0 and n0 ≥ 0 where all n ≥ n0 and f(n) ≤ cg(n). I was wondering what n0 and n are? Example: for the function f(n) = an2+ bn + ...
4
votes
2answers
3k views

DFS vs. Union Find for computing connected components of a static graph

According to CLRS, When the edges of the graph are static—not changing over time—we can compute the connected components faster by using depth-first search. However, I tried to do some runtime ...
0
votes
1answer
341 views

Time Complexity of Basic Primality Test Algorithm [duplicate]

The algorithm I'm referring to is one of the most fundamental primality checks: For a number, $n$, check if it is divisible by some odd number, $k$, less than or equal to $\sqrt{n}$. Assume $n$ is a ...

1 2 3 4 5 17