Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions

Complexity of Algorithms

Posted on 2000-04-13
Last Modified: 2010-04-02
I want to know how the complexity of the Algorithms are calculated. and depending on what values of the complexities the best algorithm is selected , lets take algorithms for sorting or searching .

Question by:babashri
  • 7
  • 3
  • 2
  • +2

Expert Comment

ID: 2711444
1. Time taken(No of comparisons)
2. Pointer(Memory) overheads to implement the solution
are a few

Author Comment

ID: 2711504
can you explain me the terms as O, log(n) or similar terms that appear in the complexities , with an example

LVL 84

Expert Comment

ID: 2714895
g(n) is O(f(n)) if thre exists a constant c such that
g(n) <= c*f(n) for all but a finite set of n > 0
Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.


Author Comment

ID: 2714919
ozo , you are using terms that are difficult to understand
Cna you explain with some example to explain th terms : 0, log ...

LVL 84

Expert Comment

ID: 2714964
e.g. log(n+2) is O(log(n)) because we can let c=log(2) so log(n+2) <= c*log(n)

Expert Comment

ID: 2717939
to find a max number in an array (with n cells) takes visiting all cells - O(n)
ofcourse each visit might take SOME operations but we will round them to one because its a CONSTANT number.
(even if its one line in C, it might be 4-5 in assembly...)

to calculate the Mul-board takes
to fill up a matrix n*n size.
each cell takes CONSTANT (O(1)) number of operation ==> O(n*n)*O(1) = O(n^2).

to explain sorting is a bit more difficult, and need some extend understanding.



Expert Comment

ID: 2722179

Let me attempt to make it a little bit simpler.

Order O(n) means that the time taken by the algorithm is proportional to n, if you are processing n items through it.
Example: linear search in an unordered array.

Order O(log n) means that the time take is proportional to log n.  
Example: Binary search in a sorted array.

Order O(n^2) means proportional to n-square. Example: Bubble Sort.

And so on.

Which algorithm suits a purpose best, depends on the expected number of items to process, n. It sometimes also depends on the sequence in which the input items come in. For example, building an unbalanced (rather, not-necessarily-balanced) binary tree by inorder traversal. Depends on the sequence of input. If the input is in ascending order, the time taken can be very large.

Hope this puts things in a simpler perspective? If you need more clarification or examples, please ask.

- stochastic

Author Comment

ID: 2722329

can you tell me how the term 'O(log n)' comes for the binary stuff?
Please explain with some example.


Expert Comment

ID: 2722588
binary finding for example.
split the problem to half each iteration.
so if you have 128 items, next iteration you will have 64
then 32, 16, 8, 4 ,2 ,1

so for given n items how many steps are needed ?
for 1 item - 0  (2^0=1)
for 2 items - 1  (2^1=2)
for 4 items - 2  (2^2=4)
for 8 items - 3  (2^3=8)

for n items - log(n)   2^(log(n)=n


Expert Comment

ID: 2722603
I hope you know how binary search works. It works by halving the scope of search each time. It starts with the middle element first, and compares the middle element with your search key. Thereafter, it reduces the scope of search to the left half (if middle element is larger than your search key) or to right half (if middle element is smaller than your search key).

It keeps doing this halving, till it finds a match, or concludes that there is no match.

Let me take a simplified example. Imagine that you have a sorted array of numbers 1 to 127 in ascending order (so n=127). Say you are searching for the key value 13. The steps of comparison will be as follows:

step 1: Searching 1..127. middle point is 64. 13<64. Take left half.  
step 2: searching 1..63. Middle point is 32. 13<32. Take left half.
step 3: searching 1..31. Middle point is 16. 13<16. Take left half.
step 4: searching 1..15. Middle point is 8. 13>8. Take right half.
Step 5: searching 9..15. Middle point is 12. 13>12. Take right half.
Step 6: searching 13..15. Middle point is 14. 13<14. Take left half.
Step 7: searching 13..14. Middle point is 13 (integer division). Found.  

So you see, we took 7 steps to do this.
Log of 128 to the base 2 is 7.

Now if you try to do this with n=256, you will see that you will need (upto) 8 steps, as Log of 256 to the base 2 is 8.

So in general, in binary search, the worst case number of comparisons you will need will be log of n to the base 2 where n is the number of items in the array.

I hope this example helps.

- stochastic.

Author Comment

ID: 2725540
Thanks stochastic,
At the last I want to ask you how we come to O(NLogN) complexity for the quick sort.

Thanks a lot

Accepted Solution

stochastic earned 20 total points
ID: 2725567

I assume you already know the algorithm or the logic for quicksort. Here is how the complexity becomes O(N*LogN):

Imagine that M = Log N to the base 2.
On the first pass, there are approximately N comparisons (actually N-1). After this, the input data splits into two sublists each of size N/2 approximately. For each of these sublists, there are approx. N/2 comparisons, resulting into a total of four sublists each of size N/4/ and so on.

After halving the sublists M times, there are N sublists each of size 1. Thus, the total number of comparisons becomes

N + 2*(N/2) + 4*(N/4) + ... + N*(N/N)
N + N + ... + N (M terms).
which is N * M which is N * LogN
(because M = Log N to the base 2).

This is how the complexity of quicksort becomes O(NLogN). Which is considerably better than O(N^2) of Bubblesort for large values of N.

Hope this finally gives you the complete answer you needed. (Whew, that was quite a bit of work for 10 points! In future, please consider giving larger points to attract more experts to yield greater variety of answers :-)

- stochastic

Author Comment

ID: 2725631
Adjusted points from 10 to 20

Author Comment

ID: 2725632
Thanks a lot stochastic ,
Hey i have increased the points , i am bit miser because i think if i exhaust all the available points , i would not be able to ask questions with 0 points
..Moreover i am not an expert too.

Author Comment

ID: 2725639
A very comprehensive answer :-))

Thanks to all

Featured Post

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Macro will not compile after project converted from IAR to Microchip xc8 (in MPLab) 3 191
List out all word 7 317
An API detour question 7 93
Super Scope, DHCP 5 91
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

860 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question