Is nlogn the Same as n Multiplied by logn?

  • Context: Undergrad 
  • Thread starter Thread starter pjhphysics
  • Start date Start date
  • Tags Tags
    Log
Click For Summary
SUMMARY

nlogn is definitively equivalent to n multiplied by log(n) in the context of Big O notation. The discussion confirms that the base of the logarithm does not affect the proportionality of the functions, as Big O notation abstracts away scalar differences. Therefore, O(log_a(x)) is equal to O(log_b(x)) for any bases a and b. This understanding is crucial for analyzing algorithmic complexity.

PREREQUISITES
  • Understanding of Big O notation
  • Familiarity with logarithmic functions
  • Basic knowledge of algorithm analysis
  • Experience with programming concepts
NEXT STEPS
  • Study the properties of logarithms in algorithm analysis
  • Learn about different bases of logarithms and their implications in Big O notation
  • Explore examples of algorithms with O(n log n) complexity
  • Investigate the relationship between logarithmic and linear functions in computational complexity
USEFUL FOR

Students, software engineers, and computer scientists interested in algorithm analysis and performance optimization will benefit from this discussion.

pjhphysics
Messages
16
Reaction score
0
Hey,

Is nlogn (or more specifically nlog[base2]n) the same as: n multiplied by logn?

Thanks
 
Mathematics news on Phys.org
Yes. In a programming, it would be written something like n * log(n).

I am guessing you're talking about Big Oh notation. An interesting thing about Big Oh is that it doesn't matter what base log you're referring to. Given two bases, log_a(x) and log_b(x) will always be proportional to each other for all x. Big Oh notation ignores scalar differences between functions, so O(log_a(x)) = O(log_b(x)).
 

Similar threads

Graduate Hey anyone please can tell me this one:A=lim(e^(1/n*logn)) (n tends
  • · Replies 4 ·
Replies
4
Views
2K
Big-O Estimate for (n*logn + 1)^2 + (logn + 1)(n^2+1) - Homework Problem
  • · Replies 1 ·
Replies
1
Views
4K
Show that n^(logc)/c^(logn) =1 as n->inf
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Solve Lagrange Multiplier Mystery: ∂Σ{Ni}/∂Nj = ∂N/∂Nj=0
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad What Does Normalization Achieve in Montgomery's Pair Correlation Conjecture?
  • · Replies 1 ·
Replies
1
Views
2K
Why does 1/[n log(n)]^1.1 converge
  • · Replies 1 ·
Replies
1
Views
3K
Find p in a Sorted Array with Unique Property | O(log n) Algorithm
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Solve Series Convergence: Cauchy's n^{th} Root Criterion
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Number of Integers (<N) divisible only by one power of 2
  • · Replies 6 ·
Replies
6
Views
1K
Big-O Notation, and reading comprehension
  • · Replies 8 ·
Replies
8
Views
11K