DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 91--------------------------------------------------
Time complexity
By: dinesh Date: November 17, 2012, 11:58 pm
---------------------------------------------------------
What is the time complexity of the following programs? Justify:
A)
void fun()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=log(i); j++)
printf("Fun");
}
B)
int foo(int n) {
if (n > 0) {
for(i=n-1; i >0;i--)
foo(i);
}
return 1;
}
#Post#: 93--------------------------------------------------
Re: Time complexity
By: dada786 Date: November 18, 2012, 12:58 am
---------------------------------------------------------
I think first ones answer is O(nlogn)
and of second one is O(2^n)
#Post#: 94--------------------------------------------------
Re: Time complexity
By: dada786 Date: November 18, 2012, 1:03 am
---------------------------------------------------------
first ones sum[sub]i=1:n[/sub](i*log(i))
#Post#: 98--------------------------------------------------
Re: Time complexity
By: ravu Date: November 18, 2012, 8:53 am
---------------------------------------------------------
For second one it is - O(2^n)
#Post#: 100--------------------------------------------------
Re: Time complexity
By: srini Date: November 18, 2012, 9:36 am
---------------------------------------------------------
For the first one,
if you find the integral of ilog(i) over 1to n, the answer is
O(n^2 logn).
#Post#: 102--------------------------------------------------
Re: Time complexity
By: kpr29 Date: November 18, 2012, 10:43 pm
---------------------------------------------------------
For the second one the answer is O(2^n-1 - 1 ) for n >
1...........
#Post#: 103--------------------------------------------------
Re: Time complexity
By: dinesh Date: November 18, 2012, 10:52 pm
---------------------------------------------------------
Time Complexity of the (A) can be written as log1 + log2 + log3
+ ... log n (number of times inner loop is executed for each i )
= log n! = nlogn
for (B)
KP is more accurate and precise...
*****************************************************