Algorithm complexity - explanation of O(log n)?

Question

I'm fairly new to complexity measures, please bear with.

I understand the following complexity examples:

O(n) - Linear Time

Example:

std::vector<int> MyV={1,4,6,2,9};
std::for_each(MyV.begin(), MyV.end(), [](int e1, int e1){return e1<e2;});
//I.e. n of operations based on the number of elements

O(1) - Constant Time

Example:

for(int i=5; i--;)
{
  //Do Stuff
}
//i.e. n of operations will be 5

O(n2) - Quadratic Time

Example:

std::vector<int> MyVec_A={1,2,3,4,5};
std::vector<int> MyVec_B={1,2,3};
for(int i=MyVec_A; i--;)
{
  for(int x=MyVec_B; x--;)
  {
    //Do Stuff
  }
}

Are the above example correct?

If not, could you provide some pointers as to how I can correct the examples?

I'm also unsure of Logarithmic time O(log n), an example would be really helpful?

Is this mistagged? Looks like C++ but you have a Haskell tag. Also, note that in `for` loops the increment statement doesn't need to be terminated with a semicolon `for(int i=5; i--) ...` instead of `for(int i=5; i--;)` — Alec, Oct 16 '16 at 18:33
@Alec according to the latest clang compiler, the ; is required for this reverse loop as opposed to: for(int 1=0; 1 — Babra Cunningham, Oct 16 '16 at 18:37
Oh yeah. I missed the fact that that was you break condition. :) As for O(log n), doing binary search on a sorted vector is O(log n). — Alec, Oct 16 '16 at 18:41
Related: http://stackoverflow.com/questions/9152890/what-would-cause-an-algorithm-to-have-olog-n-complexity/9153420#9153420 — templatetypedef, Oct 16 '16 at 18:51

gsamaras · Answer 1 · 2016-10-16T18:49:27.523

You say that your last example is O(n²), but what's n??? That's what you should ask yourself. It's usually the size of the vector that the loop runs.

The easy case would be to have:

std::vector<int> MyVec_A = {1, 2, 3, 4, 5};
std::vector<int> MyVec_B = {1, 2, 3, 4, 5};
for(int i = MyVec_A; i--;)
{
  for(int x = MyVec_B; x--;)
  {
    // Do Stuff that are of negligible complexity
  }
}

and now say confidently, the complexity of this example is: O(n²), where n is the size of MyVec_A (or MyVec_B equivalently).

Now, in your specific example, the length of the vectors differ, thus you need to change what you have. Let's say that MyVec_A has size n and ``MyVec_Bhas sizem`, then this double loop will have a time complexity of:

O(n*m)

I hope it's clear that when the vectors are of the same size, as in my example, then n = m and the complexity becomes O(n * m) = O(n * n) = O(n²).

The hello world of the logarithmic complexity is the binary search method.

Given an array of integers, you are requested to find a number that comes from user input. You can either search linearly the entire array (O(n) complexity, where n is the size of the array), or, if the array is sorted, you can find the element in O(logn), by using the Binary search algorithm. I even have an example Binary Search (C++).

BTW, learn to ask a single question (or very tightly connected subquestions to a question).

Algorithm complexity - explanation of O(log n)?

1 Answers1