Linked Questions

When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ ...

As part of my continual improvement plans, I'm reviewing algorithm analysis and I've hit a roadblock. I cannot figure out how to determine the Big O complexity of $\log(n+7)^{\log(n)}$. I've spent the ...

What notation is used to discuss the coefficients of functions in big-O notation? I have two functions: $f(x) = 7x^2 + 4x +2$ $g(x) = 3x^2 + 5x +4$ Obviously, both functions are $O(x^2)$, indeed $\...

This is an example in my lecture notes. Is this function with time complexity $O(n \log n)$?. Because the worst case is the funtion goes into else branch, and 2 ...

I learned that recursive Fibonacci is $O(2^N)$. However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or ...

I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good. However, there are faster runtimes such as (from now on just assume it ...

I was reading “Introduction to Algorithms” by CLRS and it says Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, we ...

I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem. The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$. ...

I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$ ...

I am learning from the MIT course Introduction to Algorithms. The professor says: Now, remember $\Theta(n)$ is essentially something that says "of the order of $n$". What does "of the order ...

I want to estimate with big O the following expressions: $$ \begin{align*} f_1(x) &= \frac{x^4 + x^2 + 1}{x^4 + 1}, \\ f_2(x) &= \frac{x^3 + 5 \log x}{x^4 + 1}. \end{align*} $$ How do you ...

I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know ...

I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:...

I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting. Linear Search - with time complexity $O(n)$ Matrix Addition - with time complexity $O(n^2)...

How would you determine big O notation for $\log^b x$? I don't think you can simply say $O(\log^b x)$, can you? If you can, then here is a better question: $x^3 + \log^b x$. How would you know if it'...