Is nlogn the Same as n Multiplied by logn?

  • Thread starter pjhphysics
  • Start date
  • Tags
    Log
In summary, nlogn and n x logn are two different notations for the same concept in computer science. They both represent the product of n and logn, which is commonly used to analyze the time efficiency of algorithms and data structures. nlogn is considered more efficient than polynomial time complexities, but less efficient than logarithmic or constant time complexities. nlogn is commonly used in divide and conquer algorithms and data structures such as binary search trees.
  • #1
pjhphysics
16
0
Hey,

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

Thanks
 
Mathematics news on Phys.org
  • #2
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)).
 

1. Is nlogn equal to n x logn?

Yes, nlogn and n x logn are two different notations for the same concept. They both represent the product of n and logn.

2. What is the significance of nlogn in computer science?

nlogn is a commonly used time complexity notation in computer science. It represents the time efficiency of an algorithm, specifically in cases where the input size (n) and the number of operations required (logn) are related.

3. Can nlogn ever be greater than n x logn?

No, nlogn and n x logn will always have the same value. This is because logn is the exponent of a number (n) and when multiplied by n, it results in the same expression (nlogn) regardless of the notation.

4. How does nlogn compare to other time complexities?

nlogn is considered to be more efficient than polynomial time complexities such as n^2 or n^3, but less efficient than logarithmic time complexities such as logn or constant time complexities such as 1.

5. In what situations is nlogn commonly used?

nlogn is commonly used to analyze the time efficiency of algorithms that involve divide and conquer techniques, such as merge sort and quicksort. It is also used to analyze the time complexity of certain data structures, such as binary search trees.

Similar threads

B Can a log have multiple bases?
    • General Math
2
Replies
44
Views
3K
I Finding N / log(2) and M / log(3) very close together
    • General Math
Replies
9
Views
1K
The order of complexity of the Pascal code -- like n * log(n)....
    • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
Merge sort running time O(nlogn) formula
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
B I do not understand Log tables
    • General Math
Replies
15
Views
2K
Complexity of this heap algorithm
    • Programming and Computer Science
Replies
1
Views
1K
Slope of N - t graph of radioactive decay
    • Introductory Physics Homework Help
Replies
2
Views
111
Hey anyone please can tell me this one:A=lim(e^(1/n*logn)) (n tends
    • Calculus
Replies
4
Views
2K
Number of ways to partition n persons and probability to form n groups
    • Precalculus Mathematics Homework Help
Replies
10
Views
1K
MHB Powers function n^5+n^4=(n^5−n^3)(n−1)−(n−2)
    • General Math
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top