What is mean by Logarathmic in Big O notation? Read more details?

Question

1)Linear means the algorithm takes constant time to insert an element, for example, insertion in linked list takes 1 second to insert one element.Am I right?

2)Quadratic means, it takes twice time for n amount of data, that is, for inserting 20 elements it takes 400 seconds.Am I right?

Like this say me a simple example for logarathmic.Please give me a simple example and put it in such a way I can easily understand as I have written above.

I am not preferring any links or books. If there is a good link where big O is said in a very simple manner, please give it as an additional to your wordings.

Answer 1

It's been a while, so check my work, but...

1. Constant time - Does not matter how many N you insert



2. Linear - progresses in a straight line, like Xn (2xN for example)



3. Quadratic - X^2 is an example, or maybe it is better shown as N^X



4. Logarithmic - http://www.wolframalpha.com/input/?i=Log%28x%29&asynchronous=false&equal=Submit like that, log(x)

Answer 2

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.



O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.



O(N^2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N^3), O(N^4) etc.



O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^N) function will quickly become very large.













http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Answer 3

You are partially right..These are problems related to algorithms.



Algorithms are used to solve a problem.

Algorithms have three things:



1. Input

2. Computing Function

3. Output



Big O notation is used to show the complexity of a function.



(It upper bound of complexity in technical terms. Upper bound and lower bounds relate to Mathematics more. You will come to know about these in future, as you keep on reading algo. )



First of all,complexity of a function here means computations required to solve a problem. (OR say number of comparisons done by computer.)



It can be for Insertion, Deletion or Search or Sorting. (You are considering only Insertion. )



Complexity means "Effort required to compute the result of function with respect to Your input N"



Sooo...



Big O notation shows the complexity in terms of powers of N. (You know it)



complexity of N means that,

It is linear. As N grows, Computation grows w.r.t N.



(Note that if a computer has clock speed of 3 Ghz. Then it can perform this calculation in 1/3*10^9 seconds. (Which is very small.)



So dont see time, But How it is growing with increase of input size.



Similarly, for N.log(N) It increases a bit less than N^2.



It is very logical and interesting to see how it happens..Read some articles. It is necessary.



Master method and few other methods are used to calculate it.

Algorithms by Cormen gives you very deep understanding about these.