What is O(n log n) or O(n log(log n))

Posted by Mark Tomlin on Stack Overflow See other posts from Stack Overflow or by Mark Tomlin
Published on 2010-03-20T06:06:13Z Indexed on 2010/03/20 6:11 UTC
Read the original article Hit count: 502

Filed under:

logarithm

|

numbers

|

function

|

math

What does O, if indeed it is a Oh (As in the letter O) not the number Zero (0) mean? I think the n would be number, but I'm not sure as I'm not a 'real' computer programmer, just a hobbyist. And log would be logarithmic function, but I only know that because of smarter people then I have told me this, while never really explaining what a logarithm is.

So please, in plain English, explain what this is, and the differences between the two (such as their applications.

© Stack Overflow or respective owner

Related posts about logarithm

How to find a binary logarithm very fast? (O(1) at best)

as seen on Stack Overflow - Search for 'Stack Overflow'
Is there any very fast method to find a binary logarithm of an integer number? For example, given a number x=52656145834278593348959013841835216159447547700274555627155488768 such algorithm must find y=log(x,2) which is 215. x is always a power of 2. The problem seems to be really simple. All what… >>> More
Inaccurate Logarithm in Python

as seen on Stack Overflow - Search for 'Stack Overflow'
I work daily with Python 2.4 at my company. I used the versatile logarithm function 'log' from the standard math library, and when I entered log(2**31, 2) it returned 31.000000000000004, which struck me as a bit odd. I did the same thing with other powers of 2, and it worked perfectly. I ran 'log10(2**31)… >>> More
Efficient implementation of natural logarithm (ln) and exponentiation

as seen on Stack Overflow - Search for 'Stack Overflow'
Basically, I'm looking for implementation of log() and exp() functions provided in C library <math.h>. I'm working with 8 bit microcontrollers (OKI 411 and 431). I need to calculate Mean Kinetic Temperature. The requirement is that we should be able to calculate MKT as fast as possible and with… >>> More
Implementing Operator Overloading with Logarithms in C++

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello my friends, I'm having some issues with implementing a logarithm class with operator overloading in C++. My first goal is how I would implement the changeBase method, I've been having a tough time wrapping my head around it. My secoond goal is to be able to perform an operation where the… >>> More
What is O(n log n) or O(n log(log n))

as seen on Stack Overflow - Search for 'Stack Overflow'
What does O, if indeed it is a Oh (As in the letter O) not the number Zero (0) mean? I think the n would be number, but I'm not sure as I'm not a 'real' computer programmer, just a hobbyist. And log would be logarithmic function, but I only know that because of smarter people then I have told me this… >>> More

Related posts about numbers

read numbers from files in columns, one column whole numbers, other column numbers with decimals

as seen on Stack Overflow - Search for 'Stack Overflow'
int price=' '; // attempt to grab a decimal number - but not the correct way int itemnum=' '; // attempt to grab a whole number - but not the right way while((price== (price*1.00)) && (itemnum == (itemnum*1))) What is a way to get numbers in 2 diff columns where one column is whole numbers… >>> More
C code won't compile

as seen on Stack Overflow - Search for 'Stack Overflow'
Please help me to understand why the following code will not compile: #include <stdio.h> //#include <iostream> //using namespace std; int main(void){ int i,k,x,y,run,e,r,s,m,count=0; char numbers[19][19]; for(i=0;i<19;i++){ for (k=0;k<19;k++){ numbers[i][k]='… >>> More
Regex : Matching phone numbers starting with NNN and having 10 numbers

as seen on Stack Overflow - Search for 'Stack Overflow'
I need to match phone numbers that : start with 010 or 012 or 016 or 019 Consist of 10 numbers exactly can you please help me on how to match numbers using PHP and regex thanks >>> More
How to convert sequence of numbers in an array to range of numbers

as seen on Stack Overflow - Search for 'Stack Overflow'
In javascript how to convert sequence of numbers in an array to range of numbers? eg. [2,3,4,5,10,18,19,20] to [2-5,10,18-20] >>> More
program to print odd numbers and even numbers on seperate threads

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am learning programming using pthreads. How can I write a program to print odd numbers and even numbers on separate threads. >>> More