Algorithmic Efficiency

Algorithmic Efficiency
Intro, Complexity
Finding Complexities
Best, Worst & Average Cases
-> By Apni Kaksha <-

Algorithm
Algorithm is the procedure followed for achieving the specific task.
Efficiency & Effectiveness
Effectiveness ensures that the result is achieved correctly.
Efficiency ensures that the result is achieved with using minimal energy, memory,
time, etc.
In programming, efficiency depends on :
● Speed of Computer ● Web Traffic

● Size of input ● Compiler
These are external factors which can be controlled upto some extent, but varies too much.
Internal Complexity
Internally we can tweak the program by improving two things :
1. Time taken for execution (Temporal/Time Complexity)

2. Memory required (Space Complexity)
Optimizing these two will result into faster results with lesser size.
Time Complexity
Time complexity of a program is the number of instructions that a program
executes.
print(‘Rasode me kon tha?’) time complexity = 1
for i in range(20):
print(‘Ye Rashi thi’)
time complexity = 20
Big-O Notation
Big O Notation is used to depict an algorithm’s growth rate. It checks the
algorithm’s performance as input size grows.
*O Notation is useful in comparing algorithms.
It will take at most N2 A = O(n2) B = O(2n) It will take at most 2n

steps for input size N. steps for input size N.
ooooohhh….
Comparing two Algorithms
N 1 10 20 100 1000
N2 1 100 400 10000 1000000
2N 2 1024 1048576 1.26 X 1030

Finding Complexity
C1
print(‘Binary_Search’) n=input( )
for i in range(n):
Let’s suppose it takes c1 time print(‘Binary Search’) C2
to execute this statement.
It may vary device to device. Total Time : C1 + nC2

We ignore constants.
Execution is constant. No. of executions depends on ‘n’
That’s why we write every We ignore the constant terms.

constant as 1. We write it as O(n).
We write it as O(1)
Finding Complexity
print(‘Ti’) for i in range(n) :
print(‘kT’) print(‘HI’)
print(‘ok’) for j in range(n):
print(‘LALLU’)
Let the statements take
C1 C2 C3 times respectively. It will take C1+nC2+ C3+nC4 time.
Total time = C1+C2+C3 We only write the higher exponent
But it’s constant. variable.
We write it as O(1) We write it as O(n).

Finding Complexity
Ignoring for i in range(n) : if a==b:
constants
print(‘HI’) return true
for j in range(n): else:
print(‘HEY’) for j in range(n):
print(‘Suskribe!’)
Total executions : n(C1 + nC2)
=> nC1 + n2C2 If : O(1) else : O(n)
We will take the worse one.
We write it as O(n2) We write it as O(n).
Summarized Rules
● Simple Constant Statements - O(1)
● Iteratives(no. of repetitions) - O(n)/O(n2)/O(n3)/etc.
● if/elif/else - take the worst case
● Subsequent statements - add the complexities
● Nested statements - multiply the complexities.
● In case of Function calls, time is taken only in the code of function body and
setting up the parameters(which is O(1), if a large structure is copied it is O(n)).
Logarithmic Complexity
Logarithmic Complexity means the algo. has a log factor.
It is generally found when the problem is divided into fractions (usually in ½).
e.g. Binary Search - O(logN)

At each repetition problem size was reduced to half.
How log comes?
e.g. Binary Search
Problem is divided by 2 until element is found.
In the worst case it divides until size is left 1.
Let’s suppose it takes k steps to divide till 1.
N/2k = 1
2k = N
Taking log both sides
log2(2k) = log2N
k*log2(2)=log2N [logaa =1]
k=log2N
k was the no. of executions, i.e. Time Complexity
Best is not the Best
We always try to achieve faster algorithms, but sometimes an algorithm is a

little bit faster, but it takes 2-3 times the storage and the code becomes very
complex.
Debugging, understanding becomes harder.

Best, Average & Worst Case
for e.g. Finding a number in a list.
Best Case : 0th index

Average Case : beech me kahin
Worst Case : last index
Practice Time
Q1. Linear Search vs Binary Search.
Q2. Reorder the following efficiencies from the smallest to largest :

(i) a. 2 b. N! c. n5 d.10,000 e. nlog2(n)
(ii) a. nlog2(n) b. N+n2+n3 c. 24 d.n0.5

Practice Time
Q1. Calculate the run-time effeciency :
Practice Time
Q1. Calculate the run-time effeciency :
p = -1
q=n
while(p+1)<q:
m=(p+q)/2
if A[m] > m:
p=m
else:
q=m

Algorithmic Efficiency

Uploaded by

Copyright:

Available Formats

Algorithmic Efficiency

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Algorithmic Efficiency

Uploaded by

Copyright:

Available Formats

Algorithmic Eﬃciency

-> By Apni Kaksha <-

In programming, efﬁciency depends on :

● Speed of Computer ● Web Trafﬁc

1. Time taken for execution (Temporal/Time Complexity)

print(‘Rasode me kon tha?’) time complexity = 1

*O Notation is useful in comparing algorithms.

It will take at most N2 A = O(n2) B = O(2n) It will take at most 2n

N2 1 100 400 10000 1000000

2N 2 1024 1048576 1.26 X 1030

It may vary device to device. Total Time : C1 + nC2

That’s why we write every We ignore the constant terms.

We write it as O(1) We write it as O(n).

e.g. Binary Search - O(logN)

We always try to achieve faster algorithms, but sometimes an algorithm is a

Debugging, understanding becomes harder.

Best Case : 0th index

Q2. Reorder the following efﬁciencies from the smallest to largest :

(ii) a. nlog2(n) b. N+n2+n3 c. 24 d.n0.5

You might also like