Is log(n!) = Θ(n·log(n))?

Remember that

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

You can get the upper bound by

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2)

Related Posts:

  1. What is the big-O of the function (log n)^k
  2. Big O, how do you calculate/approximate it?
  3. How to calculate big-theta
  4. Which is better: O(n log n) or O(n^2)
  5. What is O(log* N)?
  6. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  7. Are there any real O(n^n) algorithms?
  8. In a triangulated isometric grid, what triangle is a given point in?
  9. What does O(log n) mean exactly?
  10. What does O(log n) mean exactly?
  11. how to implement quick sort algorithm in C++
  12. Python: maximum recursion depth exceeded while calling a Python object
  13. Time complexity of a Priority Queue in C++
  14. Determining complexity for recursive functions (Big O notation)
  15. Example of O(n!)?
  16. O(n log n) vs O(n) — practical differences in time complexity
  17. What is tail call optimization?
  18. Big-oh vs big-theta
  19. Exactly how many comparisons does merge sort make?
  20. What is the time complexity of while loops?
  21. Intuitive explanation for why QuickSort is n log n?
  22. Calculate distance between two latitude-longitude points? (Haversine formula)
  23. How to calculate time complexity of backtracking algorithm?
  24. Difference between Big-O and Little-O Notation
  25. How to calculate an angle from three points?
  26. Why is O(n) better than O( nlog(n) )?
  27. How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
  28. Difference between Big-Theta and Big O notation in simple language
  29. How are the following functions O(N^3)?
  30. How to determine if a point is in a 2D triangle?
  31. What is tail recursion?
  32. What is a loop invariant?
  33. What is a loop invariant?
  34. Unfamiliar symbol in algorithm: what does ∀ mean? [closed]
  35. how to calculate binary search complexity
  36. When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
  37. What is Sliding Window Algorithm? Examples?
  38. Quicksort with Python
  39. What is the difference between tree depth and height?
  40. Python: maximum recursion depth exceeded while calling a Python object
  41. Understanding Time complexity calculation for Dijkstra Algorithm
  42. Why is the time complexity of both DFS and BFS O( V + E )
  43. What is stability in sorting algorithms and why is it important?
  44. Breadth First Search time complexity analysis
  45. Counting the sum of every nodes’ neighbors’ degrees?
  46. Time Complexity of the Kruskal Algorithm?
  47. Polynomial time and exponential time
  48. Insertion Sort vs. Selection Sort
  49. Difference and advantages between dijkstra & A star
  50. Best Case for Bubble Sort
  51. How to find the kth smallest element in the union of two sorted arrays?
  52. When will the worst case of Merge Sort occur?
  53. Is Quicksort in-place or not?
  54. When should I use Kruskal as opposed to Prim (and vice versa)?
  55. Trying to understand max heapify
  56. Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)
  57. Python Weighted Random [duplicate]
  58. What is the meaning of “exclusive” and “inclusive” when describing number ranges?
  59. What’s a good algorithm to generate a maze?
  60. Intuition for perceptron weight update rule
  61. Easy: Solve T(n)=T(n-1)+n by Iteration Method
  62. PacMan: what kinds of heuristics are mainly used?
  63. Quicksort vs heapsort
  64. Best case time complexity for selection sort
  65. Looking for algorithm finding euler path
  66. Trie complexity and searching
  67. What does this definition of contiguous subsequences mean?
  68. Is complexity O(log(n)) equivalent to O(sqrt(n))?
  69. How to find maximum spanning tree?
  70. Algorithm to return all combinations of k elements from n
  71. Merge sort time and space complexity
  72. Shuffle a deck of cards in Java
  73. Median of Medians in Java
  74. What is a loop invariant?
  75. Hash table runtime complexity (insert, search and delete)
  76. Quickselect time complexity explained
  77. What is the proper equivalent of “while(true)” in plain C?
  78. Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
  79. Asymptotic Notation – does n (log n) (log n) simplify?
  80. Big Oh for (n log n)
  81. Is there an O(n) integer sorting algorithm?
  82. Computational complexity of Fibonacci Sequence
  83. An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)
  84. how to write a recurrence relation for a given piece of code
  85. Why is merge sort worst case run time O (n log n)?
  86. Which algorithm is faster O(N) or O(2N)?
  87. What is the time and space complexity of a breadth first and depth first tree traversal?
  88. Create your own MD5 collisions
  89. A tool for calculating the big-O time complexity of Java code? [closed]
  90. Finding the median of an unsorted array
  91. What is the difference between bucket sort and radix sort?
  92. Time complexity of nested for-loop
  93. Finding all possible combinations of numbers to reach a given sum
  94. Sorting an array in C?
  95. Finding square root without using sqrt function?
  96. Is Dijkstra’s algorithm for directed or undirected graphs?
  97. Modular multiplicative inverse function in Python
  98. Minesweeper solving algorithm
  99. About bubble sort vs merge sort
  100. Running time of algorithm A is at least O(n²) – Why is it meaningless?

Leave a Comment