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
0
votes
1answer
55 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
114 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
97 views

Big O understanding given different input sizes

I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
1
vote
1answer
29 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 ...
3
votes
1answer
2k views

What is a computer year?

In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?
0
votes
1answer
389 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
229 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
39 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
23 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
1k 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
153 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
113 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 ...
1
vote
1answer
152 views

Is there an example of Dinitz's algorithm running with the worst time complexity?

I am trying to find a network, where Dinic's algorithm makes $|V|^2*|E|$ steps. Clearly it cannot be a network with $3$ or less vertices, but I am not able to come up with a working example for quite ...
2
votes
1answer
51 views

Finding loop invariant of Lowest common multiple function

So I have the following function: ...
1
vote
0answers
62 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 ...
6
votes
2answers
1k 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)$...
0
votes
1answer
147 views

Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?

The problem (from MIT 6.006 course) is the following: In this problem, you are given a $2D$ array of integers $A$ that has $n$ rows and $m$ columns. (Assume $m$ is much (e.g., exponentially) ...
1
vote
0answers
234 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
250 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
44 views

Adding two running time from a function

I have a method Func() that has two inner methods Func1() and Func2(). ...
4
votes
2answers
16k 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
115 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
38 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
139 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 ...
2
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 ...
0
votes
3answers
1k 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
69 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$ ...
0
votes
1answer
1k views

Time complexity of kruskal using array data structure

I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps: Sort the edges as ...
2
votes
2answers
105 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
220 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
43 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
26 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
356 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
62 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
387 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
58 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
305 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 ...
1
vote
3answers
75 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 ...
2
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
124 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
246 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 ...