95 views

### Why do we focus on asymptotics when analyzing algorithms? [duplicate]

Maybe a newbie question, but why when we analyze algorithms do we focus on asymptotics? It seems to me the performance of algorithms on finite input sizes (after all, problems are rarely infinitely ...
41 views

### Why do we consider the order of growth when analyzing algorithms? [duplicate]

Seriously why do we consider how the computation time time increase with the number of inputs as a measure of performance when we can easily measure such as program execution time,power consumption,...
283k views

### Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...
7k views

### “For small values of n, O(n) can be treated as if it's O(1)”

I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1). Example: The motivation for doing so is based on the incorrect idea that O(1) ...
2k views

### Justification for neglecting constants in Big O

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
2k views

### How can a quadratic algorithm be faster than a linearithmic one?

I have to solve the following problem: Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, ...
429 views

249 views

### What is the importance of C in big-Oh notation?

From the definition of Big Oh, it states that there should be a function $g(x)$ such that it is always greater than or equal to $f(x)$. Or $f(x) \le cg(n)$ for all values of $n > n_0$. What I'm not ...
131 views

### Are hardware specs relevant in software performance comparisons?

I notice occasionally in blogs or articles comparing different languages, algorithms, etc. that the author will divulge info about the processor used in the testing. Is this meaningful? Shouldn't ...
75 views

### How much time would be needed to compute an algorithm with time complexity $O(n^k)$?

How much time would be needed to compute a minimum k-cut, which has time complexity $O(n^k)$ on a graph with $n=5000$ and $k=30$? Consider using a basic 2GHz and 8GB RAM laptop. Please explain also ...
As far as I understand correctly, to say that a decision problem $X$ is in P means that there exists a polynomial $c\cdot n^p$ such that as $n$ goes to $\infty$, the steps required to solve $X$ is ...