Time complexity of c program

Question

I have this code:

for (int i = strlen(str) -1; i >= 0; i--)
     if (str[i] == '\t')
         str[i] = str[i+1];

And I don't know how to find the solution for time complexity (Big O). The solution should be O(n^2log(n)) or O(nlog(n)) (in worst case). Thank you for your advice.

Not related to the question, but watch out if the last character of the string is a \t: it will take something from outside of the array. — Lakshya Raj
– Lakshya Raj, Commented Jan 11, 2021 at 20:11
@Damien the strlen has some time complexity too. I think. The answers are O(n^2log(n)) or O(nlog(n)), i don't know how to achieve it. — Stepan
– Stepan, Commented Jan 12, 2021 at 14:09

Marko · Accepted Answer · 2021-02-06 19:50:44Z

1

In code above for loop has complexity of O(n) like Damien said, function strlen() has complexity of O(m)(m=string length). Since both are run only once average complexity is O(n) which is far better complexity than O((n^2)log(n))(or O(n^(2log(n))?) and also better than O(n*log(n)) so trying to achieve some of this complexities would mean trying to find worse answer(why would you do that?). If this loop is part of some bigger code(for which you should find complexity) than you should provide it in its entirety.

answered Feb 6, 2021 at 19:50

Marko

1382 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time complexity of c program

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related