0

im learning now data structure and i just write a code and i dont know very well how to compute the time complexity of the code. i need to count the frequent of words in sorted string array. i think that if i write a code with for loop thats end in (n) thats O(n) and if inside the loop there is while loop that goes until length - 1 is O(n-1) so the time complexity is O(n^2).

and this is my code. thanks for all!

int length = array.length;
for (int i = 0; i < length - 1; i++) {
int counter = 1;
while(i< length - 1 && array[i] == array[i+1]) {
    counter++;
    i++;
}
System.out.print(counter +" ");
Dolev Abuhatzira
  • 11
  • 2
  • please post your code as `code text`, not an image. – pkamb Mar 29 '20 at 19:41
  • i fixed that, thank u :) – Dolev Abuhatzira Mar 29 '20 at 19:46
  • You set counter = 1 inside the for loop. you print counter after the for loop. why the inner loop? set a variable to array[0]. loop over the remaining array. increase a counter the current array element == your remembered word. if it differs print counter and reset it to 1 and store the new word in variable. So its O(n). – Patrick Artner Mar 29 '20 at 19:49
  • It is somewhat unclear what you're. Are you asking if this algorithm is O(n^2)? If so, the answer is yes. In general though, if you want to get better at algorithmic time-space complexity, I suggest outside resources, such as this one from Khan academy: https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation – Free Url Mar 29 '20 at 20:59

1 Answers1

0

The total amount of iterations your loop executes is N-1 times, because both loops break when i exceeds N-1. However, the actual time complexity of your program depends on the lengths of the strings as well, because comparison between strings takes O(|S|) time, where |S| is the (minimum) length of the two strings being compared. So if you have a total length of strings of M, your overall time complexity will be O(N+M).

Your mistake is in assuming that nested loops always yield quadratic complexity. If you set some counter to evaluate the number of operations your code requires and test for large N, you'll find that it scales linearly rather than quadratically.

aeternalis1
  • 675
  • 4
  • 7