You are not logged in. Please login at www.codechef.com to post your questions!

×

What is Complexity Of A Code?

what do you mean by complexity of a algorithm in layman's term. How can one find it?

asked 15 Mar '15, 00:25

rishu97kr's gravatar image

2★rishu97kr
2528
accept rate: 0%


total expense per operation, evaluated over a sequence of operations.

link

answered 15 Mar '15, 02:02

rjohari23's gravatar image

3★rjohari23
779214
accept rate: 14%

and how is it calculated? what does O(n) & nO(n) means?

(15 Mar '15, 02:26) rishu97kr2★

This is known as the Big-O notation.

Briefly:
1) O(1) means in constant time - independent of the number of items,
2) O(N) means in proportion to the number of items,
3) O(log N) means a time proportional to log(N).

Basically any 'O' notation means an operation will take time up to a maximum of k*f(N) where:
k is a constant multiplier and f() is a function that depends on N.

Quick Explanation:
1) O(N) means that your algorithm will take on the order of n operations to insert an item. e.g. looping through the list once (or a constant number of times such as twice or only looping through half).

2) O(N2) means that for every insert, it takes N2 operations. i.e. 1 operation for 1 item, 4 operations for 2 items, 9 operations for 3 items and so on.
Note : Here N refers to the size of input.

Other Links : Read here for further explanation.

link

answered 15 Mar '15, 03:32

rjohari23's gravatar image

3★rjohari23
779214
accept rate: 14%

edited 15 Mar '15, 03:49

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,664
×966
×144

question asked: 15 Mar '15, 00:25

question was seen: 1,017 times

last updated: 15 Mar '15, 03:49