0

I'm struggling to wrap my head around working out big-o notation from code.

I understand the basic steps i.e.

for (int i = 0; i < n; i++) would be O(n)

And that

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

would be O(n2)

I am struggling to understand where or how to calculate the logarithmic values.

i.e.

Would :

for (int i = 0; i < n * 2; i++) be O(log n) or O(n log n) or O(log 2n) etc

Can someone please demonstrate in code form as to an example and how the notation was formed.

I have researched and keep getting examples where sorting is concerned and the lists are chopped etc, which makes sense in a form but I don't seem to get how to apply that to code as above.

I am new to the whole coding and big-o notation.

I have am familiar with objects, classes, loops, functions, structs, etc. I am busy learning c++ as it is part of my course. My text book does not explain logarithmic big-o calculations very well or pretty much at all.

ROMANIA_engineer
  • 54,432
  • 29
  • 203
  • 199
Benefit
  • 19
  • 1
  • 4

1 Answers1

1

One could represent the code as a recurrence relation:

T(n) = T(n-1) + 2 * c, where c = the inner part of the code,

which we will do 2 * n times.

Giving us solution like: T(n) = 2 c n + c_1, where c_1 a constant

And since 2 * c is a constant, and the second term, also a constant drops off, we can write:

O(n)

Darrell Ulm
  • 132
  • 1
  • 2
  • 11
  • Hello, please add some formatting to the code so it is easier to read/understand. Take a look [here](https://stackoverflow.com/help/formatting) for more info. – Chait Mar 28 '17 at 22:02