Stack Overflow
Stack Overflow

Questions tagged [little-o]

In algorithmic analysis, little-o notation is used to quantitatively state that one function grows strictly slower than another function.

Formally speaking, we say that f(n) = o(g(n)) if

limn → ∞ f(n) / g(n) = 0.

That is, the rate of growth of f(n) is strictly slower than the rate of growth of g(n).

34 questions
433
votes
5 answers

Difference between Big-O and Little-O Notation

What is the difference between Big-O notation O(n) and Little-O notation o(n)?
Jeffrey Lott
  • 7,171
  • 6
  • 28
  • 28
12
votes
3 answers

Is there any function that is in o(1)?

A colleague of mine has asked me a question: Is the set o(1) (little o notation) empty? My question is: Is o(1) an empty set? If not, is there a program that has o(1) time complexity? Reminder, definition of little-o by Cormen: A function f(n) is…
amit
  • 175,853
  • 27
  • 231
  • 333
4
votes
1 answer

Function in Big-O, but not in Little-O

I'm looking for a simple example function, f(n), that is Big-O of some other function, g(n), but is not Little-o of g(n). In other words, some f(n) such that f(n) is O(g(n)), but not o(g(n)). The simplest case I can think of is f(n) = n, g(n) = n.…
Jeffrey
  • 83
  • 5
3
votes
3 answers

If f(n) = o(g(n)) , then is 2^(f(n)) = o(2^(g(n)))?

Notice that I am asking for little-o here (see similar question here) - for big Oh it's clearly wrong - for little-o it feels right but can't seem to prove it... EDIT: glad I raised a debate :) Assume f,g > 0 for simplicity
Mr_and_Mrs_D
  • 32,208
  • 39
  • 178
  • 361
3
votes
1 answer

Which f(x) minimizes the order of g(f(x)) as x goes to infinity

Assume f(x) goes to infinity as x tends to infinity and a,b>0. Find the f(x) that yields the lowest order for as x tends to infinity. By order I mean Big O and Little o notation. I can only solve it roughly: My solution: We can say ln(1+f(x)) is…
Sus20200
  • 337
  • 3
  • 13
3
votes
3 answers

Proving if g(n) is o(f(n)), then f(n) + g(n) is Theta(f(n))

So I'm struggling with proving (or disproving) the above question. I feel like it is true, but I'm not sure how to show it. Again, the question is if g(n) is o(f(n)), then f(n) + g(n) is Theta(f(n)) Note, that is a little-o, not a big-o!!! So far,…
Wanna-be Coder
  • 169
  • 1
  • 11
2
votes
1 answer

Is little O the complement of Theta to Big O

In other words, is o(f(n)) = O(f(n)) - Θ(f(n))? f ∈ O(g) [big O] says, essentially For at least one choice of a constant k > 0, you can find a constant y such that the inequality 0 <= f(x) <= k g(x) holds for all x > y. f ∈ Θ(g) [theta] says,…
Luis Grappi
  • 87
  • 2
  • 8
2
votes
2 answers

How to complete this in O(1)

I just got this from a company for a interview test and I completed it with ease but they said that my functions were in o(n). Heres the questions Write a class IntegerTracker with these methods: track(int) - Receives an integer for tracking.…
Esko918
  • 1,397
  • 1
  • 12
  • 25
2
votes
2 answers

Confused on Little O meaning

So what I took from little o page is when you apply the small O notation we have to check if one rate is faster then the other (small o focuses on the upper bound)? In this case when we apply small o: 2^n = o(3^n) will be false as 2^n and 3^n upper…
S A
  • 827
  • 10
  • 23
2
votes
1 answer

Checking big theta, little oh and little omega with limits?

Say we have two functions f(n) and g(n). If we we wanted to check if f(n) is little oh o(g(n)) would it be valid to do the following: lim n -> infinity f(n)/g(n) and the result would have to = 0 ? So if the above comes out to 0, will it mean f(n)…
Vimzy
  • 1,871
  • 8
  • 30
  • 56
2
votes
3 answers

Exponentials: Little Oh

What does nb = o(an) (o is little oh) mean, intuitively? I am just beginning to self teach my self algorithms and I am having hard time interpreting such expressions every time I see one. Here, the way I understood is that for the function nb, the…
user3092043
  • 49
  • 1
  • 4
1
vote
2 answers

Little-oh notation in detail, CS homework, excluding actual assignment

I'm sitting here with this assignment in a course on algorithms with massive data sets and the use of Little-Oh notation has got me confused, although I'm perfectly confident with Big-Oh. I do not want a solution to the assignment, and as such I…
Casper
  • 193
  • 1
  • 2
  • 12
1
vote
1 answer

What is the guarantee for little-o to be a strict upper bound?

Whether the little-o is tight upper bound or strict upper bound? Correct the answer below if wrong, g(x) is an upper bound for f(x) that is not asymptotically tight. There is a much larger gap between the growth rates of f and g if f ∈ o(g) than if…
Iyyara
  • 11
  • 2
1
vote
7 answers

Example of an algorithm that is too time complex?

As much as i've searched online, I cannot find examples of algorithms that aren't solvable in practice due to the amount of time that they'd take to compute. I was trying to think of an example such as counting the number, size, and location of…
user5803705
1
vote
1 answer

How do I prove all constants to some exponential power belong to little-o of some function

I'm trying to prove that c2n = o((loglog n)n) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n approaches infinity, and I can very easily pick some…
Dillon Drobena
  • 761
  • 1
  • 8
  • 26
1
2 3