The Gateway to Computer Science Excellence
0 votes
134 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 by Active (2.2k points)
edited by | 134 views
0
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,209 comments
104,892 users