0

I am just trying to figure out the runtime of the code below. My thought is that time = log1 + log2 + log3 + ... + log(n-1) = log(n-1)!, but I do not know how to simplify it to big-O.

for (int i = 0; i < n; i++) {
    for (int j = i; j > 0; j /= 2){
        // statement;
    }
}
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
BigC
  • 11
  • 1
  • You got the placement of the factorial wrong, it goes inside the log. – harold Oct 07 '21 at 02:14
  • You should be able to use [some bounds on factorials](https://en.wikipedia.org/wiki/Factorial#Rate_of_growth_and_approximations_for_large_n) to come up with an answer. Looks like n log (n) to me. – President James K. Polk Oct 07 '21 at 02:16

0 Answers0