Linked Questions
42 questions linked to/from How to come up with the runtime of algorithms?
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