Given a range, I have to calculate the frequency of numbers in an array. Is the given solution efficient?

#include<iostream.h>

int main()
 {
   int a[10]={1,2,3,5,2,3,1,5,3,1};
   int i;
   int c[10]={0};

   for(i = 0 ; i < 10 ; i++)
       c[a[i]]++;

   for(i=0;i<10;i++)
      cout<<i<<": "<<c[i]<<endl;

   return 0;
 }

The running time of t开发者_Go百科he Algorithm is O(n) but its taking an extra space of O(n). Can I do better?

Thanks!

Depends on what is important to you - you can create an algorithm taking O(n^2) time, but O(1) space (using two loops, see code below), but you can't improve time complexity below O(n).

for(i=0;i<10;i++) {
  count = 0;
  for(j=0;j<10;j++)
    if (c[j] == i) count++;
  cout<<i<<": "<<count<<endl;
}

Another possiblity for O(1) space would be an in-place sort of the array and then traversing this once, which should have time complexity O(n log n) using in-place merge sort.

No you can't. That's the best you can do.

What is "efficient"? Show us you performance requirements and performance measurements. Then we can tell you if it's efficient. Until then this is a wide open question with lots of wrong answers and no right answer. The answers thus far are correct only the word 'efficient' means 'runs as fast possible'.

Maybe you have a fast computer with little RAM.

You can always make a piece of code run faster or use less memory of less disk space or less.... if it is not 'efficient' enough, I have seen guys hand craft assembly to make it faster. Usually it's a waste of time and effort. Optimizing code that has not been profiled is a fools game.

If all the numbers are in range 1 to n then in can be done in O(n) time complexity and O(1) space complexity.

if there is an index X and array A such that A[X]=Y then add N to the value present at index Y.So A[Y] becomes A[Y]=original+N. Continuing this ,values will be of form (original+KN) where k>=0.To retrieve original element we can do (original+KN)%N since (x+kn)%n=x and count can be found by (original+KN)/N.