Linked Questions
42 questions linked to/from How to come up with the runtime of algorithms?
193
votes
3
answers
25k
views
Is there a system behind the magic of algorithm analysis?
There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
- 71.6k
3
votes
2
answers
252
views
Determining Big O [duplicate]
i<--2
while (i<n)
someWork (...)
i <-- power (i,2)
done
Given that someWork(...) is an O(n) algorithm, what is the worst case
...
user3806894
-1
votes
1
answer
151
views
How to get an O(n) for a search algorithm [duplicate]
Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that x = 3y. The algorithm needs to run in linear time in the worst case.
At the ...
- 129
2
votes
1
answer
114
views
Analysis of Algorithms: Applying Concepts [duplicate]
I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application.
I ...
- 21
1
vote
1
answer
143
views
What exactly is bigO notation? [duplicate]
I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent?
I heard that there are two:
RunTime
Memory Complexity
How can I learn ...
- 113
0
votes
0
answers
82
views
How to calculate Complexity Time O()? [duplicate]
Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was.
I can solve basic problems, but whenever the problem ...
- 109
100
votes
3
answers
34k
views
How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are ...
- 1,313
4
votes
2
answers
34k
views
Time complexity of a backtrack algorithm
I've developed the following backtrack algorithm, and I'm trying to find out it time complexity.
A set of $K$ integers defines a set of modular distances between all pairs of them. In this
algorithm, ...
- 171
3
votes
2
answers
15k
views
How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?
How are asymptotical time complexities calculated for recursive algorithms?
Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
- 129
11
votes
2
answers
687
views
How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?
This a homework question from Udi Manber's book. Any hint would be nice :)
I must show that:
$n(\log_3(n))^5 = O(n^{1.2})$
I tried using Theorem 3.1 of book:
$f(n)^c = O(a^{f(n)})$ (for $c >...
- 113
0
votes
2
answers
2k
views
how to calculate time complexity of non terminating loops
I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs.
I just wondered that how to calculate time complexity of non terminating ...
user48126
0
votes
4
answers
5k
views
Proving Quicksort has a worst case of O(n²)
I am sorting the following list of numbers which is in descending order.
I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$
...
- 649
3
votes
2
answers
6k
views
Using software to calculate the complexity of an algorithm
I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
- 131
3
votes
2
answers
5k
views
What is running time of an algorithm?
What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
- 263
1
vote
2
answers
3k
views
Worst case time complexity of heap sort
I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows:
...
- 111
5
votes
2
answers
569
views
BigO, Running Time, Invariants - Learning Resources
What are some good online resources that will help me better understand BigO notation, running time & invariants?
I'm looking for lectures, interactive examples if possible.
2
votes
1
answer
3k
views
Upper Bound on Runtime of Memoized DP Algorithms
I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive functions....
- 254
1
vote
2
answers
2k
views
How to connect the math of recurrence relations to daily programming concepts
What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear ...
- 485
4
votes
1
answer
1k
views
What are elementary operations in time complexity definition?
Wikipedia gives us the following defintion of time complexity:
"In computer science, the time complexity is the computational
complexity that describes the amount of time it takes to run an
...
- 153
3
votes
1
answer
2k
views
Finding growth of "inter-recursive" functions
consider following code
int f(int x)
{
if(x<1) return 1;
else return f(x-1)+g(x);
}
int g(int x)
{
if(x<2) return 1;
else return f(x-1)+g(x/2);
}
...
- 291
2
votes
2
answers
2k
views
Recurrence for quaternary search algorithm
I have to come up with the recurrence for the quaternary search algorithm.
My initial thought is $T(n)=4T(\frac{n}{4})+c$ because the algorithm examines all four subproblems, and each is one quarter ...
- 21
4
votes
2
answers
715
views
Analysis of algorithms, 'big O' question
The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation?
Also, what about ...
user8872
2
votes
2
answers
1k
views
Finding integer square root for large integers [find asymptotic time complexity]
So I found this tasks in one book I am practicing from where it says:
"Find a divide-and-conquer algorithm for finding square roots for large integers and along this, find its asymptotic time ...
- 121
1
vote
1
answer
1k
views
Memoized Palindrome Subsequence
I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following ...
- 355
1
vote
2
answers
211
views
Reasoning on Efficiency (2)
Two algorithms to solve a particular problem can have theur efficiency compared using the $O$ and $o$ notation. However, this is very crude method, and tells us no information on how more effective ...
- 1,597
1
vote
2
answers
903
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 ...
- 13
8
votes
1
answer
493
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
1
answer
566
views
Algorithm Time complexity analysis for algorithm having two different time complexities
I'm implementing an algorithm that analyze several properties on large set of integers, the time complexity is bound to $N$ (set length) and $M$ (bits to represent the numbers). I'm having some ...
- 519
3
votes
2
answers
81
views
How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?
I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the ...
- 141
1
vote
1
answer
333
views
Computational complexity of generating a random vector
I'm new to the concept of computational complexity and trying to understand the topic in depth. I went through some references mentioned by some old questions, however, I had this question and not ...
- 13
0
votes
0
answers
249
views
Implement Immediate Smaller Element problem using Stack
Immediate Smaller Element Problem:
Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
- 101
0
votes
2
answers
99
views
How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?
This question is specifically related to
https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm
The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits ...
- 115
2
votes
1
answer
52
views
Proving complexity of computing product of matrices
If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{...
- 131
1
vote
1
answer
121
views
Big-O in computer Science [duplicate]
As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.
user13078
0
votes
1
answer
59
views
Reccurrence equation and finding suitable algorithm
I'm given the following recurrence equation:
$$\begin{align*}
T(1) &= 0\\
T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\
T(n) &= T((n+1)/2) + 1 && \...
- 103
0
votes
1
answer
98
views
Understanding time complexity of algorithm to determine if parenthesis are matching
Both these algorithms determine if all the parenthesis in a string are
balanced and properly nested.
The first algorithm uses "a constant amount of memory, regardless of the length of
the string.&...
- 13
0
votes
1
answer
80
views
Converting a algorithm to a runtime function
I need to find an upper limit for the runtime of $f(n)$.
...
- 143
1
vote
1
answer
52
views
How to calculate the basic steps in Fibonacci sequences to get nFn and n^2
I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book ...
- 659
1
vote
0
answers
65
views
Big-Oh of algorithm
I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345.
The algorithm looks like:
...
- 11
0
votes
0
answers
56
views
Time complexity of this for-loop
I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part.
...
- 125
0
votes
0
answers
31
views
Am I doing this correctly? Recurrence Relations [duplicate]
The function is this:
...
0
votes
0
answers
18
views
Big o notation for the algo [duplicate]
Asked this at programmers Stack Exchange, was recommend to ask here :
What would be the big o for the algo:
for (i=0; i < n*n; i++)
for(j=0; j<i*i; j++)
...
- 1