Linked Questions

Robert Sedgewick, at his Algorithms - Part 1 course in Coursera, states that people usually misunderstand the big-O notation when using it to show the order of growth of algorithms. Instead, he ...

I occasionally see these terms used and I'm not really sure what is meant by all of them. Is it possible for an asymptotic bound that is not Big $\Theta$ bound to be "tight"? What does it mean for ...

What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ ...

An optimized algorithm for the 3-sum problem with an input array N has O(N^2logN) however I read that the Big Omega for this ...

Let $W(n)$ and $A(n)$ denote, respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is always true? (A) $A(n) = \Omega(W(...

What would these statements mean if f(n) and g(n) are functions over natural numbers? g(n) is in Θ(f(n)). and An algorithm is in the complexity class Θ(f(n)).

My professor doesn't always know what's actually correct or wrong - he always has to think about it for a very long time and get back to the book and read the book for a long time to answer any of our ...

As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.

I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent? I heard that there are two: RunTime Memory Complexity How can I learn to ...

I'm taking my first algorithms class, and the first exam is tomorrow. I've been looking forward to this class since freshman year, but now that I'm in it the professor is less than stellar and I've ...

I am a newbie here I recently read tutorials on java about collection framework. The time complexity of various objects in reading/writing data What does it mean? ...

Let us suppose the best case running time of an algorithm is $\Theta(n \log n)$. Can the average case run time of the algorithm be $O(n \log n)$? Since $O(n\log n)$ would imply the value going even ...

I'm currently reading about algorithms and big O notation. I have come across som examples which for instance says the following: n is O(n^2) 3n^2 + 7n is O(2n^2 + n) 5n^7 is O(2^n) 3^n is not O(n^...

In popular literature, complexities are usually used in a very imprecise manner, often to describe the runtime performance of an algorithm and denoted with "$O$". My question is about these Landau ...

I am reading this paper named "Matching triangles and basing hardness on an extremely popular conjecture" in the second page of this paper there is this paragraph: Observe that the ∆-Matching-...