CODEWITHSUNDEEP
ctime-complexitybig-o
Stepan
Stepan

Reputation: 5

Time complexity of c program

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.

Upvotes: 0

Views: 85

Answers (1)

Marko
Marko

Reputation: 138

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.

Upvotes: 1

Related Questions