65 views

### Big O and constants [duplicate]

I've already asked this question on stack overflow, but guys have suggested me to ask my question here. Let's consider classic big O notation definition (proof link): The $O(f(n))$ is the set of all ...
3k views

### Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity. In practice, what is ...
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, ...
9k views

### What is the complexity of this matrix transposition?

I'm working on some exercises regarding graph theory and complexity. Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
271 views

### Why do compute time complexity for algorithms? [closed]

I read about Big-O notation with modular arithmetic. So, Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation ...
264 views

### What is the significance of a Θ-bound on the running time of Mergesort?

While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it. Given: Mergesort takes $\Theta(n \log n)$ compares to sort ...
163 views

### Reasoning on Efficiency (2)

Two algorithms to solve a particular problem can have theur efficiency compared using the $O$ and $o$ notation. However, this is very crude method, and tells us no information on how more effective ...
261 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 ...
333 views

### What is the running time of this recursive algorithm?

I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037. This is my proposed solution to compute the $n$th value: ...
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 ...
Consider I have the following recurrence $$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$ Now, by the master theorem, if we evaluate $n^{\log_{b}{a}}$, we get \$n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2....