Big-O Flashcards

1
Q

Given functions:

  • f(n) = 100n + log n
  • g(n) = n + (log n)²

Which relationship holds? (Select one)

  • [ ] f(n) = O(g(n))
  • [ ] g(n) = O(f(n))
  • [ ] f(n) = O(g(n)) and g(n) = O(f(n))
A

f(n) = O(g(n)) and g(n) = O(f(n))

  • 100n and n are dominant terms (we can ignore logs)
  • only differs by the constant so Big O-wise they are equal
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly