Click here to Skip to main content
14,969,978 members
Please Sign up or sign in to vote.
1.00/5 (3 votes)
what is the time complexity O(n) of these algorithm for the best case and worst case analysis?

int n = int.parse(console.readline());
int i=n;
while(i>1)
{
console.write(i);
i%=2;
}
______________________________________

int n = int.parse(console.readline());
int x=0;
for(int i=0;i<=n;++i)
{
for(int j=0;j<=i;++j)
{
for(k=1;k<=n;k++)
{
x++;
}
}
}

is the first one O(n) and second one O(n^3)? am i right? how that works?
Posted
Updated 21-Jul-14 15:07pm
v2
Comments
Alexis i 21-Jul-14 13:18pm
   
i know what time complexity is, and what the best,worst and average case for an algorithm's analysis mean but there is no best or worst case for these algorithms so far as i know!

the time complexity for both algorithms i think would be O(n)!
am i right?

then what does our teacher mean by asking what is the time complexity T(n) of this algorithm for the best case and worst case analysis?
Sergey Alexandrovich Kryukov 21-Jul-14 13:32pm
   
The operators worst and best are not defined. :-) The question does no make any certain sense.
—SA

1 solution

Since both "algorithms" are linear - they always take the same amount of time for a given value "n" - they are by definition always O(n)
So the best and worst case analysis is trivial: they are both the same.


Ignore that, I'm talking out my backside. I blame an absence of caffeine... :O

Neither of those is O(n) at all: and the value of n will have a big impact on the time taken to execute them.
Look at the code more carefully: how many times does the first example loop for the values of n between 0 and 10?
   
v2
Comments
Alexis i 21-Jul-14 19:22pm
   
the loop in the first example is execute just 1 time regardless of the input n
am i right?
Stefan_Lang 22-Jul-14 3:52am
   
What if n==0? ;-)

But yes, you're right: for complexity analysis the basic assumption is always n>>1 (n is considerably larger than 1)!
OriginalGriff 22-Jul-14 4:15am
   
Does it?
Are you sure?
Did you check? :laugh:

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900