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

learn more… | top users | synonyms

0
votes
0answers
22 views

How to calculate runtime for FOR and WHILE loops? [duplicate]

While there have been many questions/answers around this on stackoverflow and wikipedia, I would like to have a clearer understanding on how to calculate it in layman's terms. I will say that, yes, ...
-1
votes
0answers
40 views

Find number in Young tableau in $O(n+m)$

Give an $O(n+m)$-time algorithm to determine whether a given number is stored in a given $m\times n$ Young tableau. An $m\times n$ Young tableau is an $m\times n$ matrix such that the entries of each ...
-3
votes
2answers
78 views

If the list lengths are m and n, why does the merge take O(m+n) operations?

If I have two sorted lists. list A => 1 -> 2 -> 4 -> 11 -> 31 list B => 2 -> 31 -> 54 Now what should be the order of (sorted) merge and ...
-1
votes
0answers
47 views

Will my solution work? Interview Question

So there is an interview question on interview cake. The question is given an array, how can you get the product of all the numbers except for the listed value. So let's say the array is [4,7,13,9]. ...
1
vote
0answers
54 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
0answers
19 views

Why worst case running time of Insertion sort is $\Theta(n^2)$ [duplicate]

From Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Theorem 3.1 For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if ...
0
votes
0answers
24 views

How to calculate a specific time complexity of inverse calculation of matrix? [duplicate]

I am a green-hand in calculating the time complexity. Given a calculation as follows: \begin{equation} \mathbf{x}=\mathbf{A^T}(\mathbf{AA^T}+\lambda\mathbf{I}_n)^{-1}\mathbf{b} \end{equation} where ...
3
votes
1answer
33 views

About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]

In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations: $$\begin{gather*} C_N = N + 1 + ...
5
votes
2answers
102 views

Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs

Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with ...
1
vote
3answers
217 views

If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

I learned that recursive Fibonacci is $O(2^N)$. However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or ...
0
votes
1answer
47 views

Merge two series of sorted number, one much longer than the other

This is the problem: Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$ comparisons. I have come up ...
5
votes
2answers
92 views

How to compare the time-complexity of an optimized algorithm with that of the original?

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$). I managed to reduce the ...
0
votes
2answers
43 views

Running time analysis of a linear algorithm seems to me quadratic

I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a linear algorithm). I ...
2
votes
2answers
62 views

What is the time-complexity of histogram computation?

Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop. Pseudocode: ...
2
votes
1answer
91 views

How can I compute the time complexity of this image processing algorithm?

Well, my question is simple, I would like to compute the complexity time of an algorithm related to image processing. I simplified the algorithm ... so that we focus only on the problematic part. ...
3
votes
0answers
19 views

Running time for threshold function evaluation?

A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows: $$f(x_1, ...
1
vote
2answers
20 views

Number of operations performed in increment operators [closed]

How many operations are performed in the following in order to get a running time function of an algorithm: x = x + 1 x += 1 ...
3
votes
1answer
36 views

Running time function for an algorithm with while and for loop

I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and ...
5
votes
1answer
76 views

How does Knuth measure the running time of this program?

I'm reading "Structured Programming with go to Statements" by Knuth, and in it, he gives the following algorithm and a run-time cost analysis of some hypothetically generated code, letting $n$ stand ...
2
votes
3answers
152 views

In complexity, why do we find upper bounds, not lower bounds?

In algorithms we use to find Big-O (upper bound), Big-omega (lower bound) and Big-Theta but why we are always interested in finding upper bounds instead of lower bounds?
2
votes
2answers
69 views

Can you get O(n) with a word frequency algorithm?

By a word frequency algorithm: An algorithm gets a document as an input, and returns each unique word along with the number of times it has appeared in the document. For example: in:"Hello my name ...
2
votes
1answer
36 views

Radix sort and changing bases

I have recently learned about radix sort. I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort. Radix sort runtime ...
1
vote
2answers
109 views

Why can't hash tables provide O(n) sorting?

Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then ...
0
votes
1answer
50 views

d-ary heapsort analysis

I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we ...
1
vote
1answer
36 views

Complexity of dynamic programming algorithm for Knapsack

Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$. However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$. (Here $n$ is the ...
2
votes
3answers
82 views

What is more important in an algorithm, small runtime or small memory usage?

I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same ...
0
votes
1answer
35 views

Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster

I am trying to solve the following question There's an algorithm with time complexity $\sim c \cdot n^3$. Suppose there's another computer which is 10 times faster. How much bigger can our $n$ ...
2
votes
1answer
28 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of ...
2
votes
1answer
183 views

Mergesort with $O(n^2 \log n)$ runtime

I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 \log n)$. In our lecture we said that the runtime is $O(n \log n)$ assuming that every comparison is ...
1
vote
1answer
37 views

Complexity terminology

What is the terminology used for speaking about complexity, when we don't study it asympotically (but exactly) ? Thank you
0
votes
0answers
86 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 ...
0
votes
0answers
47 views

Calculate the computational complexity of multiplication AxAT

I need to implement an algorithm that calculates the symmetric matrix obtained by performing $A A^t$ being $A^t$ the transpose of $A$. I did my analysis from two perspectives: The first thing I ...
5
votes
1answer
152 views

Tree decomposition - Fastest algorithm in practise

I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph. I found the paper "A linear time algorithm for finding tree-decompositions of ...
0
votes
1answer
51 views

Algorithm analysis of nested loop [duplicate]

so I have this code: for (int i=1; i < n; i=i*5) for (j=i; j < n; j++) sum = i+j; And I'm wondering, what's the time complexity of this for ...
3
votes
1answer
112 views

What is the worst case running time for an algorithm that combines insertionsort and mergesort?

Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$? I was ...
2
votes
1answer
43 views

Simplifying a nested sum

I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big ...
0
votes
0answers
14 views

Runtime of this loop [duplicate]

I need some advice on how to determine the runtime of this loop : s=0 for ( i=1 , i <= 2^m ; i=i*2 ) { s++ } return s With $C_1$ = actions ...
0
votes
0answers
357 views

Best- and worst case for Mergesort using Bubblesort for small lists

Problem statement: Merge sort is so modified that for array sizes below 11, instead of recursive Merge sort, the array is sorted using Bubble sort. Will there be any good and bad cases now? Give ...
-1
votes
1answer
38 views

What is the time complexity (big O) of this nested for-loop? [duplicate]

What is the time complexity (big O) of this nested for-loop? I believe it's either O(n) or O(n^2) ...
0
votes
1answer
64 views

Suffix Tree algorithm complexity [closed]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident ...
4
votes
3answers
82 views

Why does this mergesort variant not do Θ(n) comparisons on average?

A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm: ...
1
vote
0answers
54 views

Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )

You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively. Assume that you have to ...
1
vote
0answers
65 views

Why does response time increase with throughput? [closed]

I'm seeing this pattern that the response time increases as throughput increases, and that the throughput has a peak after the response time starts rising. This seems counter-intuitive. It seems like ...
4
votes
1answer
117 views

Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint? A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...
0
votes
1answer
51 views

Searching through a heap complexity

Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the ...
-4
votes
2answers
101 views

How long would it take a computer with twice the processing power to solve a polynomial time problem?

Say I have some problem of $O\left(n^k\right)$ complexity. If I were to solve the problem on a computer $x$, it would take time $t$. Now I have a new computer $x'$, which has double the computing ...
0
votes
2answers
79 views

Is the Wall-Follower Algorithm in P?

Is the wall-follower algorithm a poly-time algorithm (for Perfect Mazes)? In particular, are there poly time algorithms for solving the Perfect Maze problems? A perfect maze has the following ...
1
vote
1answer
100 views

How do we derive the runtime cost of Karatsuba's algorithm?

I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it. I seem to have gotten about 75% of the way to the solution on my own, but ...
0
votes
0answers
16 views

Confusion with space and time usage [duplicate]

The following is my own set-up code: ...