Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
1answer
14 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
54 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
39 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
25 views

Calculating the complexity of an algorithm exercises

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
51 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
31 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
56 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
28 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
59 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 ...
1
vote
1answer
38 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 ...
0
votes
0answers
30 views

Hard Big O complexity for 3 loops [duplicate]

So this is a tricky one, i try to calculate Big O complexity for this code but I always fail.... I tried to nest SUM's or to get the number of steps for each case like: i=1 j=1 k=1 (1 step) i=2 j=1,...
1
vote
1answer
25 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
0answers
35 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 ...
1
vote
0answers
16 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
64 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
1
vote
1answer
63 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 ...
3
votes
1answer
46 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 ...
1
vote
2answers
80 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.
2
votes
1answer
62 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 ...
0
votes
1answer
81 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 ...
1
vote
2answers
430 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
36 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 ...
2
votes
1answer
49 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 ...
31
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
42 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
221 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
25 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 + ...
0
votes
1answer
22 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 ...
0
votes
1answer
59 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 ...
0
votes
1answer
57 views
1
vote
1answer
132 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
67 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
30 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
0answers
8 views

finding the complexity of a merge sort function [duplicate]

I have the following program and I'm trying to figure out it's complexity is- ...
0
votes
0answers
12 views

finding and minimizing merge sort algorithm runtime analysis

let's say I have an array of the size n,I want to divine it to k new arrays of the size n/k.-what's the running time of this step may be?**I thought since when we split an array to 2 we look at it ...
0
votes
1answer
46 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
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
21 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
10 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: ...
2
votes
2answers
47 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 ...
0
votes
0answers
23 views

Data “re-arranging” time complexity

I've done quite some data transforming recently. For instance:I have an array of JSON objects such as ...
-1
votes
1answer
25 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
1answer
27 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
21 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
36 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 ...
0
votes
1answer
31 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
81 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
66 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) =...