My friend and I were having a debate. Say you have an array of names, like such
"
Andy
Matt
Jessica
...
"

I want to read in all the names into an array, using this...

for( i=0;i

Question

My friend and I were having a debate. Say you have an array of names, like such
 "
Andy
Matt
Jessica
...
"

I want to read in all the names into an array, using this...

for( i=0;i<N; i++)
{
fscanf(fptr, "%s", array[i]);
}

I claimed that this loop had an O(N) complexity, because as N gets large, it will scale linearly. I noted that the complexity of fscanf was O(1)

My friend argued that the complexity ought to be O(M*N), where m is the length of the longest string. He claims that it will take much longer to read in dsfjfshfkjdshfskjdhf... than to read in Jim.

Who do you think is right?

anonymous · Answer

You're right

anonymous · Answer

Generally names will be betwen say 3-10 letters so I would say you are correct.

anonymous · Answer

Just to add to previous comment, the length of names will not grow as more names are added, on average they will be say 6 letters.

anonymous · Answer

I spoke with my professor, and and he said my friend was right. He said to think about it like this.

for (i=0;i<m;i++) //col
for (j=0;j<n;j++) //row
{
Read
}

And that has O(n^2) complexity. We are supposed to think of it as an array of characters, not as a list of names.

But I feel like if we do it as a list of names, then for sure, I would be right.


Thanks!