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
votes
0answers
34 views

Does a loop incremented by two run at (n+1)/2 times?

I recently started on this topic.. so I have to calculate the time complexity of a method that has another method in it and i do not know if i did it correctly.. Below is a code snippet that I tried ...
0
votes
1answer
51 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 ...
0
votes
1answer
372 views

The time complexity for finding the kth smallest number in a min-heap

Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap? I thought that we can remove the root element for k times and each time we apply heapify?...
2
votes
1answer
16 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 ...
2
votes
1answer
25 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
9 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
26 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
44 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
27 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 ...
0
votes
0answers
13 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
29 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" ...
0
votes
1answer
236 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'. ...
1
vote
2answers
180 views

What is the real reason that Bubble Sort runs at O(n) in best case?

In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only ...
2
votes
1answer
38 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
72 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
39 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
39 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 ...
1
vote
3answers
82 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 ...
1
vote
2answers
214 views

3 * O(n^2) vs O(n^3)

Currently while I was coding, I got a doubt. While I was solving a particular type of problem I found it to be solved in $O(n^3)$. I have broken that problem and solved it in $O(n^2)$. But to ...
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
19 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
39 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 ...
2
votes
2answers
53 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 ...
2
votes
2answers
381 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 ...
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 ...
3
votes
1answer
522 views

Finding potential function for dynamic array

About dynamic array, doubling it's size with every element that is beying its limit: From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ ...
1
vote
1answer
45 views
7
votes
2answers
2k views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
3
votes
1answer
490 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 ...
1
vote
1answer
108 views

Runtime analysis of prime-set computation

I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is : we are ...
0
votes
1answer
35 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: ...
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) + ...
0
votes
2answers
48 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
28 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 ...
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 ...
0
votes
2answers
102 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 ...
1
vote
0answers
59 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 ...
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
40 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, ...
0
votes
3answers
64 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$ ...
0
votes
2answers
55 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
24 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
42 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
2answers
390 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)$, ...
2
votes
4answers
417 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 ...
1
vote
1answer
44 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 ...