1

I'm new to time complexity and etc and trying to figure which algorithm is better.Might not be the best question of all time but yeah :/

Ishant Thulla
  • 11
  • 1
  • 2
    They are not just similar, [they are the same](https://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant). See https://stackoverflow.com/questions/22188851/why-is-constant-always-dropped-from-big-o-analysis – Progman Aug 18 '19 at 15:53

1 Answers1

1

If d is a constant then O(d*n) and O(n) are the same thing. This is what Big-O is all about i.e. the fact that these two are considered the same Big-O is part of the definition of Big-O.

The definition of Big-O is basically that for large n's some function f(n) is O(g(n)) if there exists a constant k such that f(n) ≤ k * g(n).

In your case, d is just absorbed by the constant k in that definition. A suitable constant k clearly exists: d*n ≤ k*nas long as k is greater than d.

jwezorek
  • 8,592
  • 1
  • 29
  • 46