15,741,310 members
See more: , +
what is the time complexity O(n) of these algorithm for the best case and worst case analysis?

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

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

## Solution 2

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
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: