Algo doubt

Question

What will be the time complexity?

voidfun()

{

int i, j;

for (i=1; i<=n; i++)

for (j=1; j<=log(i); j++)

printf("hello");

}

Comments

Is it O(log n)?

---

Why you think it should be logn

---

oh sry ... i took last term as O(log n).

For every n, inner loop run log n times.So,

log(1)+log(2)+log(3)+...log(n) = log(n!) is correct

Answer 1

Here we have to analyse like this :

For ith value ,  the inner loop runs log(i) times.

So say when i  =  2 , the inner loop runs  log(2) times ,  when i = 3 , the inner loop runs log(3) times and so on till i = n..

So time complexity  =  log(1) + log(2) + log(3) ........ + log(n)

                              =  log(1.2.3.....n)

                              =  log(n!)

                              =  nlogn - n + O(logn)  = nlogn      [  By Stirling's approximation and considering the dominant term ]

                              =  θ(nlogn)

Hence time complexity   =   θ(nlogn)

Comments

In this type of questions how we decide what to take

Theta notation or Bigoh notation

Sir ,plz explain

Answer was Θ(n log n)

---

If g(n) = theta(f(n)) these means that tight bound of g(n) is f(n).When we say tight bound it means that f(n) and g(n) can vary only in constants and not in variable terms.

Say we have n and n² , we have  n  =  O(n²) and not theta(n²)

But say f(n)  =  n² + n

            g(n)  =  n² - logn 

So dominant term in each of these is n² , so this will be considered only for relating f(n) and g(n)..Now as f(n) and g(n) both are having n² as their dominant terms , hence this suggests f(n) = Theta(g(n))..