what is the meaning of O(1), O(n), O(n*n) memory? [duplicate]

Question

Possible Duplicate:
Plain English explanation of Big O

Many times when time complexity of a algorithm is talked about, memory also comes into account. I want to know what is the meaning of big-O(1), big-O(n), big-O(n*n) memory?

And how it is related to time complexity?

Answer 1

As xmoex said:

o(1) constitutes a constant memory usage. So amount of input is inconsequential.

o(n) constitutes a linear memory usage. So more input means linearly more memory.

o(n*n) constitutes a quadratic memory usage. So more input means quadratically more memory (x^2 on average.

This measure of memory complexity in most cases is completely independent to the measure of time complexity. For computer algorithms it is important to know how the algorithm will manage both of these complexities to decide the quality of the algorithm. However both must be calculated separately. One may be more important than the other depending on your use cases and circumstances for the problem.

Answer 2

o(1) means constant average memory use, regardless the size of your input
o(n) means if you have n element you are processing, your average memory need grows linear
o(n*n) means if you have n elements you are processing, your average memory need will grow quadratic

there's a wiki article about the so called big o notation (covering little o as well...)

Answer 3

Complexity in terms of mamory mean how fast required memory size growth whilst growing a number of items to be processed. A good example is sorting algorithm.

• O(1) and O(log n) mean that whilst sorting N items algorithm requires less memory then total memory allocated for N items. (AKA in-place sorting)
• O(n) - memory consumption is linear so memory consumption growth as long as items count growth
• O(n*n) mean that algorithm requires much more additional memory.

Answer 4

Here everyone have explained the meaning of Big O notation. So , i m not going to explain that again . But i will explain u in brief.

Take any small program in which there is no loops.

{ int a=1;
print("%d",a);
}

This program will take negligible time to execute. Let, the declaration and printing take be unit time. So its time complexity will be O(1)

Another program with one loop and running for n times

{int a,i;
long n=10000000;
for(i=0;i<n;i++)
    // doing some calculations
}

As u can see here the declaration will take negligible time i.e. O(1). And if we let that line 4 will take some unit of time i.e. O(n). Then, the overall time complexity will be

O(1)+O(n)=O(n).

Now u can understand for O(n*n) i.e. for 2 loops.

For better understanding....

Finding an item in an unsorted list = O(n)

Multiplying two n-digit numbers by a simple algorithm or bubble sort =O(n*n)

Finding an item in a sorted array with a binary search =O(log n)

salesman problem with brute force = O(n!)

Answer 5

I am not sure if you mean big-O or little-O here, but I am going to answer more generally.

It means the same thing for memory as it does for time. If a function grows in memory O(1) then it uses a constant amount of memory regardless of the input size. If a function grows in O(n) it uses a linear amount, and O(n*n) it uses a quadratic amount.