Compare and contrast with Big O

Question

can anyone explain the understanding of space complexity? In your own opinion, which complexity (time or space) is more crucial in designing an algorithm?

What is the difference between O(log2N) and O(Nlog2N)?. I watched various videos regarding it but still do not understand fully.

Answer 1

Space Complexity in general is the amount of space needed to perform a particular task in your computer.

Let's say you have an array with 10 random elements and you want to return the sorted Array.

There are couple of ways you can do it

1) create a new array and store the elements in sorted manner and return new Array (this approach will take extra space and extra space typically depends upon the size of original array)

2) Sort the elements of array in-Place without using extra space/memory(this approach is recommended as it doesn't need any extra space)

Now think about the an unsorted array whose size is in Billions- if you want to retrieve the elements from array in sorted order ,you wouldn't want to create another copy of array whose Size is in Billions and send the new sorted array.

Instead you would like to modify the existing array in-place(without using extra space)

Most of the application we use in day to day life use in-place algorithms(like quicksort) where saving space is a top priority.

Difference between O(logn) and O(n*logn)

• Log(N)-->if you are doing a binary search on N(e.g 32) sorted elements,you will find your elements in at most (log32) time,which is 5 as you keep diving your array into 2 halves until you find your element.

• However N*Log(N) takes -> 32*Log(32) ~32*5 which is much bigger than 5.

Now think about the elements which are of billions in size. Ideally,your goal while writing an algorithm is to save time and space to perform a particular operation.

Log(1 Billion) is much better than 1 Billion times Log(1 Billion)

Finally,Complexity depends upon your requirements but most of the time the emphasis will be more on Time complexity rather than Space Complexity.

Answer 2

By definition if f and g are positive functions of real positive x, "g is O(f(x))" means there exists some X and some M such that for all x > X: g(x) <= M * f(x)

You can replace real x with natural n and get same definition.

In practice let's say you have some array (list, vector) and you have some task.

Let's say the array of numbers is ordered and you need to find a particular number. So you check middle of array, than you compare number you get with number you need to find and check middle or upper half of array or lower half. Then you continue until you find number of prove there is not such number. The number of attempts will be closed to log2(n), so you can say the time is O(log N) because O(log2 N) is the same.

If you go through array number by number, you have to check all elements and time will be O(n). Let's say you have a million of elements. Then in binary search you need about 20 checks, in full loop you need million. That's why difference between O(log N) and O (N) is critical.

Another example, you need to order (sort) an array. You can find a minimal element by checking all elements. Then you find second minimum by checking all expect first one, then you continue until you get largest element. The number calculations is n + (n - 1) + ... + 2 + 1 = n (n + 1) / 2 which is O (n^2).

You can also use quick sort algorithm where you combine binary search and a full loop through all elements. In this case the time will be O (n * log n)

Now lets say you have a million of elements in array. If you use first approach to sort array, the time will be closed to (10^6)^2 = 10^12 = 1,000,000,000,000 operations (actual number will be less, but count only power). The second approach will give result in 10^6 * log(10^6) which is around 10^6 * 10 = 10,000,000 (also actual number will be 20,000,000 we we do not count when we check big-O). See the difference.

Same issue with space. Let's say you need to do something with input values of user (input file) and you have no choice but keep all values in memory. In this case you need O(n) memory. However if you find a solution not too keep all values in memory, but only current input value and maybe some other technical variables, you say that you need O(1) of memory. Just compare million of bytes with several bytes to see how critical it is.

An example of task where you do not need full array is last 2 digits of product for all values given in input file. You do not need to reserve memory for the full list of values.

Answer 3

With N=1000000, Lg(N)=19.93... and N.Lg(N)=19931568.57... See the difference ?