New answers tagged runtime-analysis
1
vote
Accepted
Smallest parameter set for big-O expression
Here is a simple method to find the parameters that can be fixed so that (the problem whose worst runtime is bounded by) a big $O$-expression becomes "tractable", i.e., bounded by some ...
3
votes
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Your second idea is good, there is no need to start at $n = 1$:
You already proved that for $n\geqslant 3$, $T(n) \leqslant n - 1$.
You can now say that since $n-1 \leqslant n$ and since $T(1)\...
4
votes
Accepted
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
The problem in the question is a good example for two related principles.
Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to ...
1
vote
Time Complexity of Exponentiation Operation as per RAM Model of Computation
I just want to say first that I'm not an expert, but I find this question interesting. I will focus on integer exponentiation.
Like the OP says, intuitively, exponentiation of integers should cost $O(...
0
votes
Accepted
Difference between an exact and Big O Notation for worst case runtime
Consider the bubble sort algorithm shown below:
...
0
votes
Difference between an exact and Big O Notation for worst case runtime
If nothing precise was specified, you can enumerate all operations by type, such as addition, comparison, swap... and give a detailed account of their numbers. That assumes the the basic operations ...
2
votes
Difference between an exact and Big O Notation for worst case runtime
You can’t calculate any runtime except for some very simple model of a CPU. You can calculate the exact number of comparisons, or the exact number of operations moving array elements of a particular ...
0
votes
Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
In the recursion tree, the cost of the top level (i.e. level 0) is $n^2$. There are two nodes in level $1$, each having a cost of $(n/2)^2$; hence, the total cost of level $1$ is $n^2/2$. In level $2$...
0
votes
Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
Assume $n=16$.
Standard MergeSort involves the cost $16+2\cdot8+4\cdot4+8\cdot2$. If we divide by $n$, $1+1+1+1$.
"Quadratic" MergeSort involves $256+2\cdot64+4\cdot16+8\cdot4$. If we divide ...
Top 50 recent answers are included
Related Tags
runtime-analysis × 973algorithm-analysis × 571
algorithms × 290
time-complexity × 184
asymptotics × 139
sorting × 91
loops × 84
data-structures × 66
complexity-theory × 65
recursion × 55
graphs × 53
recurrence-relation × 52
big-o-notation × 32
quicksort × 30
average-case × 30
arrays × 27
amortized-analysis × 25
search-algorithms × 22
heaps × 22
dynamic-programming × 18
terminology × 16
reference-request × 15
landau-notation × 15
search-trees × 13
master-theorem × 13