Find the running time of the following code fragment in terms of n

QUESTION

Find the running time of the following code fragment in terms of n

int k = 0;

for(int i = 0; str[i] ! = '\0'; i ++)

  k+= strlen(str) - i ;

a) O(1)

b) O(log n)

c) O(n)

d) O(n log n)

e) O(n²)

ANSWER

c) O(n)

At the end of the string, a null character is encountered and the loop would iterate until the end of the string. Therefore the time complexity (running time)would be the size of the string.

EXPLANATION

Every character in the array will store a null character (‘\0’) at the end of the string. 

Example:

If char str[10]=”Watermelon”

 The loop will iterate from the first character to the character ‘\0’.

The time complexity is the size of the string ‘n’.

Therefore, running time (time complexity) = O(n)

The value of ‘k’ in each iteration:

k=0

1) k = k + 10 – 0 = 10

2) k = 10 + 10 – 1 = 19

3) k = 19 + 10 – 2 = 27

and so on..(Till 10 iterations)

Also Read: Write a new code in C language with given values just like this output