New answers tagged

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 ...
user avatar
  • 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)\...
user avatar
  • 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 ...
user avatar
  • 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(...
user avatar
0 votes
Accepted

Difference between an exact and Big O Notation for worst case runtime

Consider the bubble sort algorithm shown below: ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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$...
user avatar
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 ...
user avatar
  • 3,231

Top 50 recent answers are included