O Notation and coding

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

I understand the basic steps ie

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.

ie

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.

---

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 cn + 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)

链接地址: http://www.djcxy.com/p/39668.html

上一篇: 不变摊销时间

下一篇: O符号和编码