Linked Questions

8
votes
2answers
6k views

Difference between the tilde and big-O notations [duplicate]

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 ...
0
votes
1answer
2k views

What is the difference between a tight Big $O$ bound, a tight Big $\Omega$ bound and a Big $\Theta$ bound? [duplicate]

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 ...
2
votes
1answer
552 views

Making sense of asymptotic notation [duplicate]

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(...
2
votes
1answer
576 views

Big Omega of 3-Sum Algorithm [duplicate]

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 ...
-1
votes
1answer
81 views

O(2^n) runs in P… Is this true? [duplicate]

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 ...
1
vote
1answer
110 views

Big-O in computer Science [duplicate]

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.
1
vote
1answer
118 views

What exactly is bigO notation? [duplicate]

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 ...
0
votes
0answers
57 views

How do I prove that any function is O(…) /Θ(…) /Ω(…)? [duplicate]

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 ...
0
votes
1answer
40 views

complexity class of functions [duplicate]

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)).
1
vote
1answer
38 views

What is the difference between Big(O) and small(o) notations in asymptotic analysis? [duplicate]

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$ ...
0
votes
0answers
37 views

What are these notations O(1)/O(n)/O(log n)? [duplicate]

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? ...
0
votes
0answers
28 views

Can the average case of an algorithm be $O(n \log n)$ if the best case running time of an algorithm is $\Theta(n \log n)$? [duplicate]

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 ...
0
votes
0answers
20 views

Algorithms Big O notation [duplicate]

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(...
0
votes
0answers
20 views

Least upper bounds on complexities [duplicate]

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 ...
0
votes
0answers
15 views

What is the difference between $\ Ω $ , $\ Θ $ , and O , [duplicate]

What are these difference $\ Ω $ , $\ Θ $ and O ? Why $\ n^3 + 4n^2 = Ω(n^2) $ But, $\ n^3 + 4n^2 = O(n^5) $

15 30 50 per page