Is an $\mathcal{O}(n\times \text{Number of clusters})$ clustering algorithm useful?
To answer your last question: In real problems, the number of clusters $c$ is usually much less than $n$.

To compare to other algorithms, the running time of a naive implementation of the standard $k$-means algorithm is $O(ncdt)$ (here your $c$ is often called $k$, so $c=k$, and $t$ is the number of iterations needed for $k$-means to converge; $t$ is often much smaller than $n$ and roughly a small constant, but certainly not always).  There are ways to speed it up further.  It tends to be very fast in practice.

For high-dimension spaces, such as you are working in, one can also apply various dimension-reduction techniques on all the values, and then do cluster the reduced-dimension values.  This sometimes gives additional performance improvements.

To answer your first question: We can't tell you whether your algorithm is useful if you don't show us the algorithm.  Sorry, but that question just isn't well-suited for this site.  Some questions aren't, no matter how much you'd love to know the answer.

Perhaps you'd like to ask a new question about what is the state of the art in clustering for Euclidean metrics, for some class of parameters and some distribution on the inputs.  Except... make sure you go do your research first.  There's a lot that has been written on the subject of clustering, so go read about standard clustering algorithms first, and then make sure to tell us what research you've done when you ask the new question.  (In fact, you probably should have done that for this question, too...)