Big o notation runtime
Posted
by mrblippy
on Stack Overflow
See other posts from Stack Overflow
or by mrblippy
Published on 2010-03-18T08:04:18Z
Indexed on
2010/03/18
8:11 UTC
Read the original article
Hit count: 201
Hi, i have been given some code to work out big o runtimes on them, could someone tell me if i am on the right track or not??
//program1
int i, count = 0, n = 20000;
for(i = 0; i < n * n; i++)
{
count++;
}
Is that O(n^2)???
//number2
int i, inner_count = 0, n = 2000000000;
for(i = 0; i < n; i++)
{
inner_count++;
}
is this one O(n)????
//number3
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
count++;
}
}
O(n^2)?????
//number4
for(i = 0; i < n; i++)
{
for(j = 0; j < i; j++)
{
for(k = 0; k < j; k++)
{
inner_count++;
}
}
}
is that O(n^3)?????
//number5
int i, j, inner_count = 0, n = 30000;
for(i = 0; i < n; i++)
{
for(j = 0; j < i; j++)
{
inner_count++;
}
}
is that one O(n^3)?
//number6
int i, j, k, l, pseudo_inner_count = 0, n = 25;
for(i = 0; i < n; i++)
{
for(j = 0; j < i*i; j++)
{
for(k = 0; k < i*j; k++)
{
pseudo_inner_count++;
for(l = 0; l < 10; l++);
}
}
}
very confused about this one O(n^3)??
//number7
int i, j, k, pseudo_inner_count = 0, n = 16;
for(i = n; i > 1; i /= 2)
{
for(j = 0; j < n; j++)
{
pseudo_inner_count++;
for(k = 0; k < 50000000; k++);
}
}
o(n)???? (i get more lost as they get harder)
//number8
int i, j, pseudo_inner_count = 0, n = 1073741824;
for(i = n; i > 1; i /= 2)
{
pseudo_inner_count++;
for(j = 0; j < 50000000; j++);
}
O(n^2)???
If anyone could clarify these and help me understand them better i would be very grateful
-cheers
© Stack Overflow or respective owner