Solving for Time Complexity, What do the algorithms produce?

Question

I am confused as to what solving time complexity is. I understand how to determine if an algorithm is O(1) or O(n) etc. However, do you always manually solve for the running time, or does the algorithm output the running time? I am not sure what the algorithms of O(1) do???

In an exercise, I need to measure the time complexity on different sizes of arrays. Plot a graph of the run time versus the size of the input.

*does the algorithm output the running time, i'm not sure what the algorithms of O(1) do?* No. Algorithms do not output the running time. An `O(1)` algorithm runs in a constant amount of time (it is invariant to the input array). — Elliott Frisch, Feb 14 '19 at 12:18
So, you always calculate the answers manually for graph purposes? — bananalover, Feb 14 '19 at 12:20
Possible duplicate of [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — Paul Hankin, Feb 15 '19 at 16:24
@ElliottFrisch O(1) algorithms don't run in a constant amount of time, but rather they run in a bounded amount of time. (For example, a hash table lookup runs in O(1) time on average, but it's not constant). — Paul Hankin, Feb 15 '19 at 16:26

score 1 · Answer 1 · answered Feb 14 '19 at 12:42

Let's consider worst case complexity (notation 'O'), and with time complexity we don't actually calculate the time as it can very from problem to problem then how to determine which algorithm is better? The thought process is, Run time is varying depending upon different sample size that is 'n'. Now the question comes up how much it is dependent upon n. And in worst/best/average case how much scanning it will require to do based upon that we give it as

n , log(n) , nlog(n)....

Let's say for any problem let it be your graph problem and ask in worst case your code is going to do how many iteration of each node.Then with that you can arrive at complexity.

2n , 3n are regarded as n complexity why? , because our initial assumption is n>>

Only way to learn is ask yourself this question and deduce it on paper then try to match, slowly you will be able to figure it out seeing the pattern in algotithm.

score 1 · Answer 2 · answered Feb 14 '19 at 13:03

O() notation is calculated on how many instructions will execute in worst case. Suppose you have a program where you have this following loop -

for(int i = 0; i < n; i++)
{
  //some operation
}

So this loop will run n times. So the time complexity will be O(n).

Now suppose your program has two for loop -

for(int i = 0; i < n; i++)
{
  //some operation
}
for(int i = 0; i < n; i++)
{
  //some operation
}

So, the time complexity will be O(n+n) or O(2n). But in asymptotic notation or O() notation, we generally ignore any constant part. So we will simply say the time complexity is O(n).

Now, diving down a bit deeper. Suppose you have the following program -

for(int i = 0; i < n; i++)
{
  for(int i = 0; i < n; i++)
  {
    //some operation
  }
}

So, let's calculate how many instruction will run ultimately. It's n*n or n^2. So the time complexity will be O(n^2). Similarly if there are three or more nested loop, we will simply calculate how many instructions will run ultimately.

Now what O(1) is? - you should understand by now - if the total number of instruction is 1 or any other constant number, it's O(1).

What about O(logn) - take binary search for example. In binary search, we are cutting our array into two half. So mathematically the maximum time a binary search can run over an array of length is logn. So our time complexity is O(logn)

These are some basic techniques. Obviously there are a lot many variations. But the gist is - how many operation/instruction will run in worst case.

score 0 · Accepted Answer · answered Feb 15 '19 at 16:05

The time complexity calculation is actually manual. You are looking into an algorithm and figure out the runtime complexity of that algorithm that you have written. The algorithm does not output the time complexity.

As you have mentioned, you understand how to determine the complexity of an algorithm, I think for the exercise you need to plot a graph which is something like the following.

The exercise might want you to plot a graph which shows based on input size, how your algorithm will perform (i.e. how much time it will take).

The running time complexity is nothing but a measurement or forecasting on how your algorithm will perform based on the given input size. In the case of O(1), your algorithm will always provide the desired result in a fixed time which has nothing to do with the input size.

Understanding O(1) running time:

For example, I wrote an O(1) algorithm which takes 5 seconds to provide a result for a single input. Now if the algorithm is provided with 100 data point as inputs (i.e. input size is 100) the algorithm will take exactly 5 seconds. Then, if the input size is 99999, it will still take 5 seconds to provide the expected result.

Understanding O(n) running time:

Now let us take an example of an algorithm which is O(n) - this provides the expected output for a single input is 2 seconds. Now the increase in input size will increase the running time of this algorithm. For example, if the input size is 10 here, the running time will be 20 seconds, for 500 input size, the running time will be 1000 seconds.

I hope you get the idea. You just have to draw a graph which shows the time required to run an algorithm based on your input size.

Hope that helps!

Solving for Time Complexity, What do the algorithms produce?

3 Answers3