Time complexity (Advance Level)

Question

The difference of time Complexity between given functions can be represented by:

void fun1(int n) {     for(int i=1;i<=n;i++)      for(int j=1;j<=i*i;j++)      if(j%i==0)         for(int k=1;k<=j;k++)          s++;     return 0; }

void fun2(int n) {     for(int i=1;i<=n;i++)      for(int j=1;j<=i*i;j++)         for(int k=1;k<=j;k++)          s++;     return 0; }

$i. O(n^2)$

$ii. O(n)$

$iii.O(1)$

$iv. O(n^{1.5})$

Comments

https://gateoverflow.in/230638/ace-algorithms

---

Shaik Masthan

For the first function number of time, the inner loop will execute will be 

$\frac{n^{2}*(n+1)}{2}$

So, the complexity will be O(n^3).

---

did you checked the link ?

---

I didn't sum up all the terms. Just a calculation mistake.

O(n^4) is right.

---

@Shaik MasthanCan u please tell me what is the meaning of difference of time complexity between functions here?

---

if f$_1$ is O(n$^k$) and f$_2$ is O(n$^p$) then we can say the difference is O(n$^{|k-p|}$)

---

 

For f1 time complexity see this : https://gateoverflow.in/230638/ace-algorithms

Answer 1

According to me,

for function fun1 complexity is O(n^4) and for fun2 its O(n^5)

hence difference being 0(n)