find the time complexity

Question

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)

Comments

yes, in the given code, it should be O(n).

But there is a typo in j = i.

If instead j = 1, then answer would have been nlogn

---

thanks for confirming:-)

Answer 1

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

Comments

for i=1 how 1<=log(1) ?? the condition will be false it won't execute even once