Algorithm Analysis For Beginners

randerson112358

Jul 26, 2018·4 min read

Here we are going to apply algorithm analysis to a problem. We are given an image processing algorithm that takes O(n³) time to execute and filter an n by n or (n x n) pixel picture.

It takes 8 seconds for the algorithm to process a 1024 x 1024 pixel picture. How long will it take for the algorithm to process a 1536 x 1536 pixel picture ?

Let’s get right to it and let ‘T’ be a function of time that takes in some input that we will call ‘n’. More specifically ‘T’ is the time that it takes the algorithm to process a n x n pixel, such that we get T(n). For Example:

T(n)

T(n) is O(n³) according to the statement “we are given an image processing algorithm that takes O(n³) time to execute and filter an n x n pixel picture.” For example:

T(n) = O(n³)

When we say a function is O(n³), what we are stating is that the function grows less than or equal to a constant times n³, such that we get the following:

T(n) ≤ C*n³ whenever n > 0

We can now rewrite our equation to look like the following, since ‘T’ will is less than or equal to C * n³:

T(n) = C* n³

Now according to the problem, the algorithm takes 8 seconds to execute or run when the input size is 1024 x 1024, so we can set up our equation/function and solve for our constant value ‘C’ using this information:

T(1024) = C * (1024)³ = 8 seconds
C = 8 seconds / (1024)³

So our function T(n) = 8 seconds / (1024)³ * n³

Now that we have solved for ‘C’, we can answer the question, “how long will it take for the algorithm to process a 1536 x 1536 pixel picture” by putting the input into the function:

T(n) = 8 seconds / (1024)³ * n³
T(1536) = 8 seconds / (1024)³ * (1536)³
T(1536) =(1536)³/ (1024)³ * 8 seconds
T(1536) =(1536/ 1024)³ * 8 seconds
T(1536) =(3/2)³ * 8 seconds
T(1536) =27/8 * 8 seconds
T(1536) = 27 seconds

Now we know that the time it would take this algorithm to process a 1536 x 1536 pixel picture is no more than 27 seconds.

That’s it, that’s the answer if you would like to see this problem worked out on video , you can watch the below video:

If you would like to learn more about Algorithm Analysis , you can take my online course here. I also have a course on Udemy.com called Recurrence Relation Made Easy where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. You can check out my YouTube channel of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Computer Science Website:

Udemy Videos on Algortithm Analysis: