0

Given two algorithms to solve a problem, one with time complexity O(log(N!)) and another with O(N), which of the two will be faster?

adi
  • 143
  • 11
  • Please show your own attempt at solving this. – n. m. could be an AI Jul 17 '21 at 10:27
  • Your [guess](https://www.wolframalpha.com/input/?i=is+log2%28700%21%29+bigger+than+log2%28700%29+%3F) ? do [edit] to include the [details](https://meta.stackoverflow.com/questions/261592/how-much-research-effort-is-expected-of-stack-overflow-users).. – p._phidot_ Jul 17 '21 at 10:29
  • Aside from the duped question solving the interesting part of this question, you can't say which of two algorithms is faster given only big-O information. Big O gives eventual upper bounds (up to a constant multiple), which says nothing about actual performance without additional assumptions or information (for example, that the given big-O bounds are actually big-Theta bounds, as is often the case). – Paul Hankin Jul 17 '21 at 10:33

1 Answers1

3

O(log(n!)) Is the same as O(n*log(n)), so O(n) has the better worst-case.

See also https://stackoverflow.com/questions/2095395/is-logn-Θn-logn

Adam Millerchip
  • 20,844
  • 5
  • 51
  • 74