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
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
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
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 ...
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.
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
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
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
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
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
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
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
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
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
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