Linked Questions

16 votes
2 answers
12k 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 ...
thyago stall's user avatar
1 vote
1 answer
5k 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 ...
user3450277's user avatar
1 vote
1 answer
3k 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$ ...
smiley's user avatar
  • 21
2 votes
1 answer
1k 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 ...
Dominic Farolino's user avatar
2 votes
1 answer
742 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(...
user1745866's user avatar
0 votes
1 answer
556 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)).
wick123's user avatar
-1 votes
1 answer
287 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 ...
Hank's user avatar
  • 1
1 vote
1 answer
125 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.
user avatar
1 vote
1 answer
144 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 ...
Alpha Mineron's user avatar
0 votes
0 answers
76 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 ...
Jared's user avatar
  • 101
0 votes
0 answers
39 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? ...
MaheshVarma's user avatar
0 votes
0 answers
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 ...
ephemeral's user avatar
  • 101
0 votes
0 answers
22 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(...
James L's user avatar
0 votes
0 answers
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 ...
David's user avatar
  • 101
0 votes
0 answers
15 views

graphs notations [duplicate]

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-...
user avatar

15 30 50 per page
1
2 3 4 5
8