search
Log In
0 votes
220 views

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})$

in Algorithms
edited by
220 views
0

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).

0
did you checked the link ?
0
I didn't sum up all the terms. Just a calculation mistake.

O(n^4) is right.
0

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

0
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|}$)
0

 

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

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
178 views
I am unable to Find its time complexity using Iterative method… Will any one help me out with this . Thank you :)
asked Jan 18, 2019 in Algorithms Nandkishor3939 178 views
0 votes
0 answers
2
160 views
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?
asked Jan 6, 2019 in Algorithms Markzuck 160 views
0 votes
1 answer
3
734 views
What will be the worst case time complexity for the following code segment? int count=0,N; for(i=0;i<N*2;i++){ for(j=0;j<i/3;i++){ for(k=0;k<j*j;k++){ count++; } } } Options: O(N^4) O(N^3) O(N^2) O(N)
asked Jan 4, 2019 in Algorithms saptarshiDey 734 views
0 votes
0 answers
4
243 views
cant we write the recurrance relation for bar() as T(n) = 5T(n-1) + c, like cant we take both the recurrance call as combined as both have same parameter? and if not, then how to solve such?
asked Dec 29, 2018 in Algorithms Markzuck 243 views
...