help needed in understanding the complexity in case of if-else,while within for loop.

mscoder · 09-23-2011, 11:48 AM

Code:

for(i=0;i<n;i++)
{
while(..some conditions...){}
}
}

Code:

for(i=0;i<n;i++)
{
if(...){}
else{}
}

Code:

if(....)
{
if(..){}
}

Please help me have a clear idea as what would be the time complexities of such code segments in my code..or please share a link for the same..thanx in advance for your help..

millgates · 09-23-2011, 12:09 PM

I would guess (and I may be wrong) that in first example, the complexity would be n times the complexity of the inner loop as long as the number of iterations in the inner loop does not depend on i.
In the second example, the complexity should be n since the body of if statement is executed at most once.
The third example does not contain any loops, so the time required to execute it will be some constant value.