Big O operation

Question

Describe any operation that takes O(1) time.

The above is pretty much the question (not technically i know) but it's what i've been asked to do. My answer is the following:

An O(1) operation could be to run a loop a constant amount of time, for instance:

Sum = 0;
for (int i = 0; i < 10; i++) {   // i<10 runs 11 times, i++ runs 10 times
Sum++;                           //sum++ runs 10 times
}

The above is an algorithm so no need to be too technical with coding :)
total operation count:

sum = 0;           //runs 1 time  
for (int i=0;      // runs 1 time  
i<10;              //runs 11 times  
i++;               //runs 10 times  
sum++              //runs 10 times

The algorithm above has O(1) time complexity because the operations are run constant times. if we were to run the loop n times (e.g. i < n)- where n equals to the amount of elements in the array- the complexity would then be O(N) because then the loop would run n times meaning the iteration of loop is directly proportional to the data input in array (i know i have not implemented array in the code but this is to just make you think of that approach).
it's not homework or such. I have come to that solution and even tried to work out O(N) complexity...

@HakanSerce sorry forgot to mention that the answer is "Describe any operation that takes O(1) time." well, at least, it's what my tutor asked me to do. — , Mar 16 '14 at 08:00
You provided an answer already, do you want us to verify it? — Hakan Serce, Mar 16 '14 at 08:02
Well it could also be a 1 billion , it would still logically be O(1). That's a clear example, of why O is not the best method of measuring complexity at lower granularity. Anyways, your code is O(1) — chettyharish, Mar 16 '14 at 08:03
@HakanSerce yes please! And is the approach okay for O(n) time complexity? as i described in my answer e.g. i — , Mar 16 '14 at 08:04
Your O(1) example and analysis looks fine. Also your O(N) reasoning is correct. — Hakan Serce, Mar 16 '14 at 08:07
@chettyharish i agree but i've only been asked to provide a simple and basic answer so it's what i came up with after a long revision session — , Mar 16 '14 at 08:07
Your reasoning is correct, but remember that a O(1) function is also O(N) so there is no need of another code. — chettyharish, Mar 16 '14 at 08:08
@chettyharish sorry but could you elaborate please? do you mean to say- i don't require the use of array for o(n) because as long as the loop runs n times, it's O(n)?? — , Mar 16 '14 at 08:10
O() means a function which upper bound the time it will take for a code to run. For instance lets assume that O(1) means that it will maximum take 1 step to complete the program. Now O(N) means that it will take maximum N steps to run the program. Now since N>1 , O(N)>O(1) . So logically if your program runs below O(1) it will also run below O(N). Similarly O(1) program is also O(N), O(NlogN), O(N^2), O(2^N) and so on. — chettyharish, Mar 16 '14 at 08:19
Since I believe you are a beginner, you can try this lecture https://www.youtube.com/watch?v=ei-A_wy5Yxw. It will teach you everything you will ever need. (Its 48 minutes long and can sometimes be boring) — chettyharish, Mar 16 '14 at 08:28
Related - [What does "in constant time" imply?](http://stackoverflow.com/q/4332595) — Bernhard Barker, Mar 16 '14 at 10:47

score 3 · Answer 1 · answered Mar 16 '14 at 08:14

This answer aims to show you another angle of time complexity.

Note that when talking about time complexity, you also need to specify what analysis you are using, and O(1) time complexity can be very different according to the analysis you are asking.

Have a look at the code snap:

r = 1
while (r == 1):
   r = rand(2) //random number: 0 or 1
   //do some O(1) things

The above code will run in O(1) average time. Why? Because the probability to invoke the loop k (or more) times is 1/2^(k-1).
This gives us the complexity of

CONST*1/2 + CONST*1/4 + ... + CONST*1/2^(k-1) + ... =
= CONST* (1/2 + 1/4 + ... + 1/2^(k-1) + ... )
<= CONST * 1

So, we got that the loop is indeed O(1) run time on average case analysis, but it is easy to see that for each time t there is probability p>0 that the run time will exceed t - giving us O(infinity) worst case.

Bhavesh Munot · Answer 2 · 2014-03-16T08:50:03.243

I will give you the simplest example: Consider you are given an array of n elements and you are asked to return kth element in array where k

Code:

int function(int arr[], int n)
{ 
    int k;
    scanf("%d", &k);
    return arr[k];
}

Also other examples of O(1) complexity problems can be: 1) Adding an element to top of stack (or queue) 2) Removing an element from stack (or queue) 3) Inserting the element in linked list at front 4) Deleting an element from front of linked list

and many more...

Roman · Accepted Answer · 2014-03-16T08:25:38.380

0

An O(1) operation is one which will take a constant time not depending on the input size.

Thus, if for example you would take an array of size N and output the sum of 5 first elements, it would run in O(1) time.

edited Mar 16 '14 at 08:25

answered Mar 16 '14 at 08:10

Roman

4,443
14
56
81

Note that it depends on the language and the arguments semantic. If the language passes the array by value - it will be O(n). – amit Mar 16 '14 at 08:16
You're absolutely right :) But we're talking from an algorithm stand point - so I guess it should pass. – Roman Mar 16 '14 at 08:17
The general concept is right, it's just the word 'method' that is problematic without this comment - because this is language dependent. – amit Mar 16 '14 at 08:22

Big O operation

3 Answers3