Skip to main content

Measuring Efficiency of Algorithms

Hello
it is long time since last time I wrote a blog post , I'm Okay and passion to write more and more posts , I'll talk about measuring efficiency of Algorithms .

there exist two approaches :

  1. using the Concept of bench mark we focus on two aspects :
    • is the output of the program correct ?
    • how much time and resources are needed by the program to produce the correct output?
  2. estimate ! DON'T MEASURE , and we will talk about this approach in details in the next sections. 
discussing approach (bench mark) cost money , resources and time, it used for small problems or execution time relatively  small ,this push us - computer scientists not me of course - directly to find  a new way , estimation of execution time.

we gonna use a new term " Asymptotic Analysis  ":

Asymptotic analysis is an analytical approach to analyze the running time of the algorithms under the following assumptions  :

  • the size of the input .
  • estimating the number of steps required to run an Algorithm we neglect the primitive operations.
Asymptotic analysis is based on the growth of the function , and it tries to predict the behavior of the algorithm in the limit  i.e when the problem size is large or grows to infinity.

there exist many notation used for estimating performance in asymptomatic analysis  :-

  1. Big O notation .
  2. small o notation .
  3. Big Theta notation .
  4. Big Omega notation.
  5. small omega notation .
I'll discuss the Big Oh , informally big oh represents a set of functions that grow no faster than function , i.e.

  •  1000 , 5 n , log (n) , 1/2 n are all Big-Oh of n,  O ( n )
  • 10 , 2n , n^2 , 10000 n^2 are all O (n^2)
we use big-Oh to classify algorithms according to their Growth ( running time )

  • Constant growing function O (1)
  • Logarithmic growing function O ( log n)
  • Linear growing function O ( n )
  • n log n growing function O ( n log n )
  • Quadratic   growing function O (n^2)
  • Polynomial growing function O ( n^k ) where k is constant 
  • Exponential growing function O (2^n)
the Big Oh measure the upper bound of the function in other words it measure the worst case , the maximum running time for an algorithm .

The Formal Definition of the Big - Oh 


  • We say that t(n)=O(f(n)) if and only if there are two nonnegative constants no and c such that t(n)≤cf(n) for all n≥no and c>0
    • The expression t(n)=O(f(n)) is read as
    • T of n is in Big-Oh of f of n,
    • T of n is in the set Big-Oh of f of n,” or
    • T of n is Big-Oh of f of n.
  • The definition means that if the problem size n equals or exceeds no, t(n) will be bounded from above by cf(n), i.e. the value cf(n) will eventually exceed the value of t(n) when n>=no
there exist two approaches to show that a function t ( n ) is in O ( n ) 

  1. By showing that there exists two nonnegative numbers no and c such that t(n) ≤ cf(n) for all n ≥ no 
  2. For really large n, we can use the limit theorem to show that there exists a nonnegative number c<∞ such that


example  1 : 




 example 2 :



example 3 :


example 4 :

I finished Big-Oh in shaa Allah I'll complete the others soon , I hope you like the Article , and if you like it please can you share it .


this Article main source is PhD / Ahmed Kamal lecture slide , thank you for reading :)



to be Continued ........................





Comments

Post a Comment

Popular posts from this blog

DevExpress C# Chart Tutorial

Hello , this blog post about Charting in DevExpress , I faced many problems I visited hundreds of pages to solve this problems , actually it was the first time I use DevExpress Charts, Work is not like school or university , in school if you don't know thing you can learn it any time you want , in work you have to do today task yesterday, I like to share my knowledge and skills with you , I hope this Post help you . // clear series on chart  chart.Series.Clear(); // clear Titles of chart chart.Titles.Clear(); // legend alignment  chart.Legend.AlignmentHorizontal = LegendAlignmentHorizontal.Center; chart.Legend.AlignmentVertical = LegendAlignmentVertical.Bottom; chart.Legend.Direction = LegendDirection.LeftToRight; // creating series // series view Type example Line DevExpress.XtraCharts.Series series = new DevExpress.XtraCharts.Series("series name ", ViewType.Line); // add title  DevExpress.XtraCharts.ChartTitle chtTitle = new DevExpress.XtraCharts.Cha...
3 comments
Read more

Recursion

Recursion is a programming technique which function calls itself , this seems strange , however it is one of the most interested and effective technique in programming. it helps you write code in less statements and provides unique conceptual frame work to solve problems. lets discus some problems to know how it works : first example Triangular Numbers : it is series like : 1,3,6,10,15,21........ etc our program should get the nth term in the series, the numbers in this series called triangular numbers due to they can be visualized as a triangle. triangular numbers fig 1 finding the nth term using a loop see this figure : loop adding 1+2+3+4 and so on code is easy  , a loop will add numbers from n to 0 like this int triangle(int n) { int total = 0; while(n > 0) // until n is 1 { total = total + n; // add n (column height) to total --n; // decrement column height } return total; } it easy enough and for sure it is fast . before we start the recu...
2 comments
Read more

LeetCode Problem #19 Remove Nth Node From End of List

Solution for LeetCode Problem #19 Remove Nth Node From End of List it is linked list problem can be solved with multiple solutions, but I'm gonna solve it with fastest solution in java. Problem link we should assign dummy_head it is common while solving linked list problems  Assign 2 iterators slow and fast both equals to dummy_head we don't know the length of the list but we know it is always valid, so we will move with a window of size n+1 when we reach the end by the fast iterator the slow iterator will be in the node n+1 from the last , right? we will assign slow.next to be equal slow.next.next we are dropping the node n from last, got it? we will return dummy_head.next Thank you, AhmedG
Post a Comment
Read more