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.