CareerCup

the statement 3) runs till n^2... thus making the while logic O(n^2) which is not intended.

lets look at the complexity:
1: O(1) //assume
2: A loop that runs for each element i.e. n ==> O(n)
3. A loop that traverses through each element of arr whose size is n^2, no matter what the datatype of arr is the loop will run sizeof(arr) times i.e. n^2 => O(n^2)
total complexity: O(n) + O(n^2) ==> O(n^2)
please reply if my understanding is wrong or if there's something missing in the algo. thanks

no dude, it`s 2n solution, not n^2. And 2n has O(n) complexity, constant (2) is ommited

how can you say its 0(2n) if you are using a loop till n^2
You stupid.... You should not answer the questions ,if you dont know anything about complexity.

Listen here, you idiot, it`s not my code above and you go now to the first post and see once again the task. LENGTH of array is N, not N^2. You don`t have to go till N^2 cause its range of elements, jackass. For decision we have to have additional array which size is N^2, but time complexity is O(n), go and learn complexity, boy.

I am confused here. At the risk of being called stupid/idiot let me say.
My understanding of O(n^2)
Something like as below. As n increases the number of loops needed increases by a factor of ^2.

for( ; i<n; ++i )
{
  for( j; j<n; ++j )
  {
  }
}

In the question, the range of values is till n^2, so as number of elements increases, by definition in the question, the range of value increases by a proportion of ^2.
After the first loop the values are still not sorted.
The second loop goes makes n^2 iterations, here the number of iterations increases by a factor of ^2. And the second loop is needed for the sort to complete.

Tell me if I am missing something.

I think you`re right, for one have to go through n^2 array, complexity will be O(n^2). Counting sort can`t dmake it in O(n) here.

If input array has uniform distribution of it`s data then a pocket sort may be used.

If i am getting right, someone proposed an additional array of size n^2 so that you read elements one by one from the original array and put them in new array according to the index(assuming no duplicates). But while reading back the sorted array you have to again read n^2 spaces in new array. That still makes complexity of n^2.

The above strategy works when you have to sort n numbers in [0:m] where m = O(n)

Yes, thats right. Its O(n^2)
If can just have a single loop till n^2 and say its O(n), I could have a bubble sort. :)

int j = 0;
for( int k = 0; k < n^2; ++k )
{
  int i = k%n;
  if( a[i] > a[j] )
  {
    swap(a[i], a[j]);
  }
  if( ++j == n )
  {
    j = 0;
  }
}

Task is: try to sort in O(N), forget about O(nlogn) for a moment. There`s no need to be expert to know radix and pocket sortings, it`s algorithms` abc.

the magic of bound n^2 is that you can divide each number to 2 parts, lower bits and higher bits. For example, for n ranges from 0...7, can be represented by 3 bits, n^2 ranges from 0...8^2-1=63 can be represented by 6 bits. Then you can first sort the lower 3 bits using counting sort, with O(n), then sort the higher 3 bits later with another O(n), which bring O(n) totally. Check Radix sort for more information if you would like.

a small correction, the complexity is O(n*logn), how?
well.. this is a specific case you described.
For n = 7, complexity is O(3n+3n) = O(n*2log8)-> O(n*2logn)
For n = 127, complexity is O(7n+7n) = O(n*2log128)-> O(n*2logn)
For n = 8191, complexity is O(13n+13n) = O(n*2log8192)-> O(n*2logn)

As you can infer, complexity is O(n*2logn) -> O(n*logn)

My bad, if you are using counting sort for sorting the bits then it is O(n+k) where k = log2(n)
it is still and not O(n), rather than dividing into bits why not use counting sort directly? which should still be O(n+k)

the key point here is what is k? when you use counting sort directly, k=O(n^2). However, when you divide into 2 parts by using counting sort twice, in each counting sort, k=O(n). That is why you get O(n) finally.

so you sort the lower and then higher, fine . how do you combine these together?

to be simple, we take 2 digits integers for example, such as array A=[25,33,15,47,56,18]. First we sort the number based on the lower digits and get B=[33,25,15,56,47,18], the lower digits' order is 3,5,5,6,7,8. Next we sort the new array based on the high digits, to get C=[
15,18,25,33,47,56], this time the higher digit's order is 1,1,2,3,4,5. Since the counting sort is stable, we get the same order as in B for those that has the same number in high digits, like 15,18.

I hope it's clear, but if it's still not, check the following link,
oopweb.com/Algorithms/Documents/AnimatedAlgorithms/VolumeFrames.html
look up item 5 Radix Sort by Woi Ang to view Animation.

In the worst case, all of the numbers are in one binary tree, then you have O(log(n)).

i agree with nj's method.... if worst case, all elements end up in a single location, then inorder traversal of that bst will take O(n)..

overall retrieving, building tree n placing in original array (alongwith traversal) wont exceed O(n)..

I am assuming you are talking about a BST and not just a binary tree. Whatever the case, in the worst case, just to form the BST itself will take O(nlogn).

What if all the elements fall in same bucket?

Hi..
I guess this wont work in all cases.
x/y is a double right?
So the algo works upto the precision of double
x/y and q/y can both give same number up to some precision.
They will only be different for infinite precision.

But still that occurs rarely. So we can use radix sort when that occurs,i.e if two double precision digits are same. This gives average complexity of O(n).
But still worst case pie(nlogn)

I dont think Radix sort will work because it needs all the numbers to have same number of digits...
I dont think we can use say 1 as 0001.

I dont think Radix sort will work because it needs all the numbers to have same number of digits...
I dont think we can use say 1 as 0001.

Guys, Convert numbers to base 2 from base 10..and then do a radix sort - O(n)

I meant convert to Base N

This isn't correct