Big O operation [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this 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...

Answer 1

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.

Answer 2

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.

Answer 3

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...