Question on Big Oh notation

[OPzCatchMee]

Sorry if this is not the right place to ask this.

We say that f(n) is Big-O of g(n), written f(n) = O(g(n)), if there exists positive constants c and x such that f(n) <= cg(n) for all n <= x.
Determine the Big O notation for the following algorithm.

#include <iostream>
using namespace std;

int main()
{
int m = 0;
int n = 10;

//************ Begin algorithm ********************

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

//************ End algorithm ********************

cout << "Big O notion is ";

//Insert notation in place of "?". Output example: cout << "O(?)";
//NO SPACES!
cout << "O(?)";

return 0;
}

Should I be replacing "cout << "O(?);" with "cout << O(N^2);"?
Thanks in advance!

[ne555]

¿how did you arrive to that answer?

[OPzCatchMee]

m = i*i
The big O notion is N^2?
If it is not correct. Can show explain to me?
Thanks!

[JLBorges]

//************ Begin algorithm ********************

// int i = 0 ; initialise int: constant time, say c1
// i < n ; compare integers and jump: constant time, say c2
// i++ increment integer: constant time, say c3
// m = i*i ; multiply two integers, assign result to integer: constant time, say c4  

for ( int i = 0 /* once */ ; i < n /* n times */ ; i++ /* n times */ )
       m = i*i; /* n times */

// let the constant C = c2 + c3 + c4
// complexity: c1 + n*c2 + n*c3 + n*c4 == c1 + n*C == O(1) + O(n) == O(n)

//************ End algorithm ********************     

[OPzCatchMee]

Can you explain how you got O(n)?
Shouldn't it be O(N^2) because i*i.

[JLBorges]

Do you see that the step m = i*i ; is executed n times?
Or do you have a doubt about that?

[OPzCatchMee]

So I know that n is executed 10 times so its
m = 1*1
m = 2*2
m = 3*3
m = 4*4
m = 5*5
m = 6*6
m = 7*7
m = 8*8
m = 9*9
m = 10*10
m = 2n
and we dont need the constant of 2 so it becomes O(n)?

[JLBorges]

> we dont need the constant of 2 so it becomes O(n)?

Yes.

Where k₁, k₂ and k₃ are non-zero constants,

If the time taken is k₁ + k₂*n => linear, O(n)

If the time taken is k₁ + k₂*n + k₃*n² => quadratic, O(n²)

[OPzCatchMee]

I got it.
Thanks you for the help!