big O complexity

0 ragmar thomas · September 20, 2014

for(int i = 0; i < 1; i++)
for(int j = 0; j < 1; j++)
a = i;

what is the big O of this fragment code.
i said it will be O(n2), but my teacher said it is O(n)

for(int i = 0; i < n*n; i++)
for(int j = 0; j <= i; j++)
a = i;

and for this one i said it is O(n3), but my teacher said  it is O(n2)
is there any one who can help me understand that i am wrong, i can't admit it.
I just did it in an assumption that all arithmetic and logical operations will be computed onces and for each nested loop there will be an extra n.

Post a Reply


Oldest  Newest  Rating
0 Franz Schmidt · September 20, 2014
You are right for each nested loop there would be an extra n, BUT:
You say
a = i;

So the nested loop doesn't effect the a.

You would be right if you do:
0 ragmar thomas · September 22, 2014
no no with out the respect of

a = i;

that it possible that for every for loop whether

for(int i = 0; i < 1; i++)


for(int i = 0; i < n; i++)

it will be counted as n, since it is true for the first case that is

i = 0; and i < 1; or i < n;

this is true and for this matter it will be said n times so the complexity is  n.
long story short i have heard and read that every loop whether for or while is counted as n times, if the first condition is true and the statement in it executed once or n times. hope 'm right.
  • 1

Other Computer Related


Anything else technology related including search engines, social networking, marketing, and more!

Bucky Roberts Administrator