Exact function and Big-O of a segment of code.

[qann23]

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");
}
}
}

[Duthomhas]

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.