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 ...
- 32.9k
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)\...
- 6,942
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 ...
- 32.9k
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(...
- 835
0
votes
Accepted
Difference between an exact and Big O Notation for worst case runtime
Consider the bubble sort algorithm shown below:
...
- 1,005
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 ...
- 3,231
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 ...
- 24.9k
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$...
- 1,005
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 ...
- 3,231
Top 50 recent answers are included