edited by
1,282 views
1 votes
1 votes

What is the time complexity of the following function foo()
 

void foo() {
  int i, j;
  for(i = 1; i <= n ; i++)
    for(j = i; j <= log(i); j++)
      printf(“gate”);
}


 

  • what is the time complexity?

  • the answer given is nlogn.
  • but I think it should be O(n)
edited by

1 Answer

0 votes
0 votes
It should be nlogn only.

When the value of i is 1-----runs for log1 times

When I is 2 log 2 times

When i is 3 log 3 times

.

.

 

When i is  n log n times

So total times it runs is log1 + log 2+log 3+...logn =logn!= nLogn

Related questions

0 votes
0 votes
0 answers
1
Naveen Kumar 3 asked Nov 3, 2018
931 views
Suppose, we have an array of n elements. find the time complexity to search two elements x, y such that:-a) x+y < 100b) x+y 1000Also, state the algorithm/approach for th...
2 votes
2 votes
1 answer
2
1 votes
1 votes
0 answers
3
1 votes
1 votes
2 answers
4
sh!va asked Dec 4, 2016
928 views
for (int i = 1; i <=m; i += c){ -do something -}for (int i = 1; i <=n; i += c){ -do something - }What will the the tiem complexity of given code pseudococde?A. O (m...