We’re rewarding the question askers & reputations are being recalculated! Read more.

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
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 ...
2
votes
1answer
286 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
234 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
75 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
55 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
76 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
93 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
105 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
3
votes
1answer
71 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
93 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
206 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
1k 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
50 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
78 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
1k 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
126 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
187 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 ...
0
votes
0answers
17 views

calculate the complexity of binary search algorithm [duplicate]

How do i calculate the complexity of this algorithm at the best case and its complexity at the worst case and the average complexity by assuming that the probability that the element is in the list is ...
1
vote
1answer
302 views

Does an algorithm exist for scheduling jobs on two processors?

I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found ...
1
vote
2answers
485 views

Complexity of multiplying matrix

Let's consider the following algorithm to multiply squares matrix: A is a matrix of NxN. ...
2
votes
2answers
53 views

Inserting at the head of a linked list is O(1), but this involves moving pointers, and they are not constant size

I don't understand how linked list insertion is constant time. The larger the list gets, the more bits are required to specify memory locations, and then the more bits that must be edited to account ...
2
votes
2answers
113 views

Data structure optimized for merging maps on partitions

My question is a request for literature or pointers that address the following abstracted problem. If I have a finite set (ex. {1..10}) over which I'd like to ...
1
vote
1answer
1k views

Runtime analysis of while-loop analysis

s = n while (s > 4) s = s / 2 else s = s - 1 Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs. $S(n)=1 + S(n/2)$ if $n$ is even $S(n)=...
0
votes
1answer
134 views

Algorithm Comparison with Theta-notation

We consider two algorithms, Algo1 and Algo2, that solve the same problem. For any input of size n, Algo1 takes time $T_1(n)$ and Algo2 takes time $T_2(n)$. Prove or disprove each of the following ...
1
vote
1answer
49 views

What is the asymptotic time complexity of the following 2 recurrences?

$$T(n) = (\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$ and $$T(n) = (n\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$ for any given $i$ and $k$. I think it helps to know ...
0
votes
1answer
248 views

How to calculate complexity of an algorithm which calls a subroutine?

Consider the following example: Algorithm $A$ has Algorithm $B$ as its subroutine. The running time of algorithm $A$ without counting the time spent running the algorithm $B$ subroutine is $O(n^4)$. ...
0
votes
0answers
81 views
0
votes
0answers
16 views

Worst runtime of Delaunay triangulation algorithm [duplicate]

I am a math major without a strong background in theoretical computer science and I have to show that the worst case running time of the Delaunay algorithm is $O(n^2)$, when I know that the expected ...
2
votes
1answer
91 views

Big Oh notation for a function with two inputs of linear growth

I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function: ...
1
vote
1answer
18 views

Understanding the closed form derivation on the function f(n/3) + n^2 +3

I have the function: $$ f(n) = \begin {cases} 4 & , n = 1 \\ f(\frac{n}{3}) + n^2 -3 & , n \ge2 \end {cases} $$ The given solutions shows the unwinding of the function as follows: ...
-1
votes
1answer
34 views

Little bit confusing to compute time complexity of nested loop [duplicate]

1 for(i=1; i<=n; i++){ 2 for(j=1; j<=n; j*=2){ 3 a[i][j]=b[i][j-1]+1; 4 } 5 } line 1 : n+1 times lnie 2 : n/2+1 times line 3 : constant time c ...
0
votes
2answers
4k views

Time complexity to check if there is an edge between two nodes in an adjacency list

I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why ...
0
votes
1answer
31 views

Computation time of a Binom matlab (or C) routine

I am trying to write a Matlab (or C) routine for the exact probability F of observing K or more successes when a success probability P is expected ($\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$). I am ...
0
votes
0answers
144 views

Recursive euclid algorithm for gcd complexity [duplicate]

I am trying to calculate the complexity of the euclidean algorithm for finding the greatest common divisor (gcd) (recursive version). Here's the pseudo code: ...
3
votes
1answer
40 views

Saving time finding a result by guessing first?

I am currently taking a graduate course about Image Processing in electrical engineering and while this question doesn't particularly relate to the class itself but rather some concepts in the ...
2
votes
0answers
642 views

DPLL time complexity analysis

Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. ...
0
votes
1answer
62 views

Intuitive way to understand “Run-Length Encoding”

Run-Length Encoding is the simple form of lossless data compression in which compression in which runs (execution) of data are stored as a single data value and count rather than as the original run (...
0
votes
0answers
183 views

Doubt on analysis on time and space complexity of creating n² tuples

This is a question from a past-yr mid-term paper from my school(using Python language). Attached below is a diagram to show how a robot will move. Don't mind if the link seems dubious as I just used ...
2
votes
1answer
219 views

Exact Analysis of the Merge Sort

When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is: $T(n) =...
8
votes
1answer
120 views

What counts as an operation?

Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all ...
0
votes
2answers
49 views

Is every algorithm on bounded resources O(1)

Suppose that I have a restricted Turing Machine - it has finite tape and takes bounded input. Consider a program that halts on every input (which is at most $k$ bits). The set of inputs is finite, ...
1
vote
2answers
4k views

Time complexity of Prim's algorithm

There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix). As far as I have understood,that is because we have to ckeck all the nodes per every ...
-1
votes
2answers
11k views

What is the time complexity of the following program?

Please help me calculate the time complexity of the following program. int fun (int n) { if (n <= 2) return 1; else return fun(sqrt(n)) + n; } ...
0
votes
2answers
23 views

Runtime analysis of bit operations

In class we have learned that division takes O($k^2$) where k is the bitlength of the numbers used in the operation. What would be the runtime of a function that looks like this? ...