search
Log In
0 votes
154 views

If both of the algorithms A and B need O(nlogn) time then they
both are equally efficient and finish in same amount of time.

TRUE OR FALSE

in Algorithms 154 views
0
it should be true..
0

@SHUBHAM SHASTRI

what happens if we take A = O(n) and B = O(n log n), then also given statement is true?

Otherwise i can't take like that?

2

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

{

    count++;

}

time complexity is O(n) =O(n2) =O(n3)

But we generally denote with O(n) but it doesn't mean T(n) = O(n2) is wrong., it is also correct.

0
yes yes ..i got it ..you are correct ..
0
My doubt is that even if both algorithm has tightest upper bound as nlogn still it doesn't mean they will take exactly equal amount of time. It's approximation. Isn't it?
0
yes
0
So it should be false ?
1
When w write O(nlogn) we don.t write the constant like O(nlogn+n) or O(nlogn*k) k is constant

Consider a real-life example the best case of Quicksort is faster than heap and merge because of constant associated with it

1 Answer

3 votes

Measuring  the time complexity and the exact time are two different things, the asymptotic  notations gives us  approximation about the dependency of the number of steps with respect to the input size and the the exact time can be measured using the system clock .

The answer is false.

0
nicely written,but change the color of the font please,its unreadable

Related questions

0 votes
1 answer
1
207 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 207 views
0 votes
0 answers
2
188 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 188 views
0 votes
0 answers
3
284 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})$
asked Jan 4, 2019 in Algorithms shreyansh jain 284 views
0 votes
1 answer
4
977 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 977 views
...