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

learn more… | top users | synonyms

1
vote
2answers
93 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
22 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 ...
-3
votes
0answers
25 views

Why does the formula hold?

I am looking at the proof that the randomized quick-select algorithm runs in expected $O(n)$ time. Could you explain me why the formula $t(n) \leq bn \cdot g(n)+t \left( \frac{3n}{4} \right)$ ...
1
vote
1answer
26 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
75 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
34 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
23 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
173 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
33 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
50 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
35 views

Calculate the computational complexity of multiplication AxAT

I need to implement an algorithm that calculates the symmetric matrix obtained by performing AXAt being At the transpose of A. I did my analysis from two perspectives: (1) The first thing I notice ...
5
votes
1answer
117 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
47 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
79 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
37 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
181 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
35 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
46 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
80 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
53 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
30 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
114 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
45 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
94 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
59 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 ...
0
votes
1answer
84 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: ...
1
vote
2answers
65 views

Cost of shifting a number

I was wondering what would be a time complexity of shifting a binary or a decimal number? For example: 0011, when I shift it left I get 0001. I was thinking that the time complexity is $\Theta(n)$, ...
0
votes
0answers
20 views

Runtime and space usage of a snippet of code [duplicate]

I've been trying to understand time complexity and space complexity by writing my own snippets of code and solving them. Can you see if I'm correct? ...
0
votes
0answers
28 views

Asymptotic analysis of shifting/multiplying

I am currently working on the asymptotic analysis of Karatsuba algorithm and I have this line "return (X * B^ (2 * m)) + ((Z) * B ^ (m)) + (Y)" where X,Z,Y are ...
1
vote
1answer
26 views

Big-O Time Complexity of nested for loops [duplicate]

My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3): ...
2
votes
1answer
64 views

Kosaraju's algorithm's time complexity

I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that using an adjacency list representation gives a time complexity of ...
-2
votes
1answer
54 views

Finding the time complexity of fibonacci sequence [closed]

I tried it as follows and would like to know if it is correct.
0
votes
1answer
62 views

Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
0
votes
0answers
79 views

Count comparisons in insertion sort that uses binary search to find correct postion

Assume a list $L$ is to be sorted using the following variation of insertion sort: For $2 \le i \le n$, to insert key $L[i]$ do a binary search on the list $L[1..i-1]$ to find the correct position. ...
0
votes
1answer
71 views

Average Time Complexity of Searching An Array [closed]

Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must ...
1
vote
1answer
40 views

Verifying a solution vs. finding one

There is an algorithmic problem $A(n)$, where $n$ is the size of the problem. It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ ...
1
vote
0answers
37 views

Given an algorithm, what are the probabilities for its run-time cases?

I am given this algorithm And I am also given the fact that $1 \leq k \leq n$. If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the ...
1
vote
1answer
78 views

How to write recurrence relation for the following scenario?

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function $g(x)$ for each node x. If the cost of computing $g(x)$ is min{no. of leaf-nodes in ...
0
votes
1answer
89 views

What is “potential speedup” in parallel computing?

There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy I wonder how "potential speedup" ...
1
vote
1answer
126 views

Time Complexity proof for Segment Tree implementation of the ranged sum problem

I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here. However I'm not able to prove ...
1
vote
1answer
40 views

How to compute time complexity of a program if the time complexity of a function called inside a loop is known? [duplicate]

This is the question- Let $A[1,....,n]$ ba an array storing a bit $(1\,\,or\,\,0)$ at each location, and $f(m)$ is a function whose time complexity is $\theta(m)$. Consider the following program - ...
0
votes
3answers
57 views

Can the runtime of functions with no loops change with the number of calls?

How can we perform time complexity analysis on a function that has no loops? int somefunction(int param) { if (something) do this; else do this; } ...
2
votes
1answer
57 views

Precise runtime of the algorithm to find number of digits in an integer

Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm ...
1
vote
2answers
2k views

Why does randomized Quicksort have O(n log n) worst-case runtime cost?

Randomized Quick Sort is an extension of Quick Sort in which pivot element is chosen randomly. What can be the worst case time complexity of this algo. According to me it should be $O(n^2)$. Worst ...
3
votes
1answer
101 views

Heapsort for sorted input

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.) Here is what I have done so far ... For the ...
1
vote
1answer
50 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
-3
votes
1answer
126 views

Complexity Analysis for a nested loop with two methods [duplicate]

Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be ...