# Computation Complexity of stream algorithm

I want to analyze a clustering algorithm that clusters data stream. Since the stream can be unbounded, I cannot write O(N^2), or explicitly denote the size of the stream. How can I use the arrival rate of the data for the computation complexity? Do you have any other idea for correct analysis of stream computation (for clustering problems)?

Thank's

• In final analysis, your algorithm computation complexity depends on what? What is your computation complexity per new arrived item? This will give you the time complexity per N-items arrived till now or in total, if this is the maximum stream length. (It is just a multiplication) – Curious_Dim Jan 25 '18 at 16:07
• I can't understand what exactly your question is. I suggest you do some background reading about streaming algorithms and online algorithms (e.g., en.wikipedia.org/wiki/Streaming_algorithm) and then see if you can formulate a more specific question. Those fields certainly measure the running time of algorithms. – D.W. Jan 25 '18 at 18:30

One standard way to measure the running time of streaming algorithms is to count the amount of time taken per item that the algorithm processes. For instance, one algorithm might take $O(1)$ time per item.