This is part 1 of a two part series. Skip over to part 2 you'd like .

For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting algorithm A takes 1, 2, 4, 16, 32, and so on seconds to sort 1, 2, 3, 4, 5, and so on elements and sorting algorithm B takes 1, 2, 3, 4, 5, and so on seconds for the same. The former algorithm would be considered exponential time or O(2^n) and the latter linear time O(n). Note that exponential time is really bad because for just 30 elements, you'd be talking about 12,427 hours of compute time. Instead of actually measuring the execution time of an already implemented algorithm, we can calculate a rough model for it via asymptotic notation.

First, to analyze the complexity of algorithms, there is a need to be precise: Are you interested in complexity in the worst case or average case? There is also best case performance, but you touch that less frequently. Some algorithms such as quicksort have good average cases (O(n log n) for quicksort) but poor worst case (O(n^2)). For interviews, usually the interviewer is interested in worst-case complexity, but if in doubt, ask. Before going further, let's get a good working definition of the most common form complexity analysis: Big O notation. Big O is the asymptotic upper bound of the growth of complexity.

Some common Big-O classes are, in the order of efficiency: O(1) constant < O(log n) logarithmic < O(n) linear < O(n log n) < O(n^2) quadratic < O(n^3) cubic < ... < O(2^n) exponential < ... < O(n!) factorial.

"Big-O" Class | Name | Representative algorithms |
---|---|---|

O(1) | constant-time | insertion into a linked list, lookup of a hash table with no collisions |

O(log n) | logarithmic-time | binary search on sorted array |

O(n) | linear-time | linear search, counting sort, iterate thru array a constant number of times, Boyer-Moore string search |

O(n log n) | quasilinear time | mergesort, heapsort worst case, quicksort avg case, comparison-based sort, Dijkstra's shortest path (nonnegative edge weights) |

O(n^2) | quadratic-time | |

O(n^3) | cubic-time | Floyd-Warshall all-pairs shortest-path algorithm, Bellman-Ford |

O(n^k) | polynomial-time | dynamic programming |

O(2^n) | exponential-time | backtracking algorithm |

O(n!) | factorial-time | brute-force search traveling salesman |

I ‘d mention that most of us visitors are endowed to exist in a fabulous place with very many wonderful individuals with very helpful things.

ReplyDeletebig data training in chennai

Thanks for post:

ReplyDeleteship tÃ´́c Ä‘Ã´̣ tÆ¡́i Puerto Rico

ship chÆ°́ng tÆ°̀ sang Puerto Rico

bao tay quang chau

order dien thoai trung quoc

Very informative, your writing style is totally different from other, keep continuing.

ReplyDeleteSelenium Training in Chennai

Big Data Training in Chennai

Digital Marketing Course in tambaram

Digital Marketing Training in Velachery

Learned a lot from your blog. Good creation and hats off to the creativity of your mind. Share more like this.

ReplyDeletePython Training

Python Training Institute in Chennai

Best Python Training in Chennai

DevOps Training in Chennai

AWS Training in Chennai

R Training in Chennai

I liked your blog.Thanks for your interest in sharing your ideas.keep doing more.

ReplyDeleteIELTS Coaching in T Nagar | IELTS Training in T Nagar | IELTS Classes in Mylapore Chennai | IELTS Classes in Vadapalani | IELTS Class in Kodambakkam | IELTS Classes in Chennai Saidapet

I am really enjoying reading your well written articles.

ReplyDeleteIt looks like you spend a lot of effort and time on your blog.

I have bookmarked it and I am looking forward to reading new articles. Keep up the good work..

Best IELTS Coaching in Chennai

IELTS Coaching Center in Chennai

IELTS Coaching Center in Mumbai

Best IELTS Coaching Centers in Chennai

IELTS Classes in Chennai

I wondered upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I’ll be subscribing to your feed and I hope you post again soon.

ReplyDeleteHadoop Training in Chennai

Hadoop Course in Chennai

best big data training in chennai

Big Data Hadoop Training

Hadoop training institutes in chennai

hadoop big data training in chennai

It is very useful to me. Thank you for sharing this tips.

ReplyDeleteBest Oracle Training Institute in Chennai | Best Oracle Training in Chennai | Oracle Training Center in Chennai | Oracle Institute in Chennai

Thanks for your interesting ideas.the informations in this blog is very much useful

ReplyDeletefor me to improve my knowledge.

Best Java Training Institutes in Bangalore

Java Training institute in Anna Nagar

Java Training Institute in Vadapalani

Java Courses in OMR

Nice articles posted. It's useful for developing my skill. Keep sharing the articles!!!

ReplyDeleteData Science Training in Chennai Velachery

Data Science Training in Tnagar

Data Science Training in Nungambakkam

Data Science Training in Saidapet

Data Science Training in Amjikarai

Awwsome informative blog ,Very good information thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.

ReplyDeleteAviation Academy in Chennai | Aviation Courses in Chennai | Best Aviation Academy in Chennai | Aviation Institute in Chennai | Aviation Training in Chennai

Great post! This is very useful for me and gain more information, Thanks for sharing with us.

ReplyDeleteEnglish Speaking Course in Chennai

Spoken English Training center in Chennai

Spoken English Classes in Anna Nagar

Amazing Post. You style of writing is very unique.Pls keep on updating.

ReplyDeleteOverseas Education Consultants in Chennai

Study Abroad Consultants in Chennai

Best Overseas Education Consultants in Chennai

Abroad Education Consultants in Chennai

Overseas Education Consultants in Chennai

List of Overseas Education Consultants in Chennai

Best Consultancy in Chennai for Abroad Studies

Overseas Education Consultants

Study Abroad Consultants

good work done and keep update more.i like your information's and

ReplyDeletethat is very much useful for readers.

AWS Training Institutes in Bangalore

AWS Training in Thirumangalam

AWS Training in Amjikarai

It is very excellent blog and useful article thank you for sharing with us, keep posting.

ReplyDeleteEthical Hacking

Hacking Course in Chennai

Ethical Hacking Training in Chennai

Certified Ethical HackingCours in Chennai

Thank you for such amazing post. Keep up the good work.

ReplyDeleteSAS Training in Chennai

SAS Course in Chennai

SAS Training Institutes in Chennai

SAS Institute in Chennai

SAS Training Chennai

SAS Training Institute in Chennai

SAS Courses in Chennai

ReplyDeleteThanks for a marvelous posting! I definitely enjoyed reading it, you could be a great author.I like your post.

PHP Institutes in Bangalore

Best PHP Training in Bangalore

PHP Training in Nolambur

PHP Course in Chennai

PHP Course in Nungambakkam

PHP Training in Saidapet

PHP Course in Kelambakkam

PHP Training in Karappakkam

Thank you for sharing this post.

ReplyDeleteglobalpayrollexpert

Guest posting sites

Great Articles, i am reading regularly very helpful for develop my knowledge. Thank you for this information. I would you like to more updates.

ReplyDeleteBlue Prism Training Centers in Bangalore

Blue Prism Institute in Bangalore

Blue Prism Training Institute in Bangalore

Blue Prism Training in Nolambur

Blue Prism Course in Adyar

Blue Prism Training in Mogappair

Nice articles posted. Keep sharing the articles. I appreciate you sharing this article. Really thank you!

ReplyDeleteWeb Designing Course in Chennai Velachery

Web Designing Training in Tnagar

Web Designing Course in Nungambakkam

Web Designing Training in Kelambakkam

Web Designing Training in Karappakkam

Web Designing Course in Padur

Such an excellent and interesting blog, do post like this more with more information, this was very useful, Thank you.

ReplyDeleteAir hostess training in Chennai

Air Hostess Training Institute in chennai

air hostess institute in chennai

best air hostess training institute in chennai