What is the function class of these 2 codes? I'm thinking O(N^2) for both of them.

int mystery3(int n){

int s = 0;

for (int i=1; i<=n; i++) {

int ci = 0;

for (int j=1; j<=i; j++){

ci+=1;

}

s += ci;

}

return s;

}

void say_hello(int n){

for (int i = 1; i <= n; i++) {

for (int j = i; j <= n; j++) {

puts("hello");

}

}

}

int mystery3(int n){

int s = 0;

for (int i=1; i<=n; i++) {

int ci = 0;

for (int j=1; j<=i; j++){

ci+=1;

}

s += ci;

}

return s;

}

void say_hello(int n){

for (int i = 1; i <= n; i++) {

for (int j = i; j <= n; j++) {

puts("hello");

}

}

}

Last edited on

O(f(n)) counts worst case behavior; assume n = ∞.

All you need to care about is counting loops.

No loops → O(1).

One loop that counts over every n → O(n).

A loop that reduces the amount of processing by half (or better) → O(log n).

(Otherwise you are still at O(n).

Nested loops → multiplication. So an O(log n) loop inside an O(n) loop is O(n log n).

Hint: both of your functions have the same complexity. Do you see why?

For further reading, you can find a pretty good “Plain English explanation of Big-O Notation” over at SO:

https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation/487278#487278

I know I have seen a*fabulously excellent* explanation somewhere, but I do not recall where, alas.

I hope this helps.

All you need to care about is counting loops.

No loops → O(1).

One loop that counts over every n → O(n).

A loop that reduces the amount of processing by half (or better) → O(log n).

(Otherwise you are still at O(n).

Nested loops → multiplication. So an O(log n) loop inside an O(n) loop is O(n log n).

Hint: both of your functions have the same complexity. Do you see why?

For further reading, you can find a pretty good “Plain English explanation of Big-O Notation” over at SO:

https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation/487278#487278

I know I have seen a

I hope this helps.

Topic archived. No new replies allowed.