ScaleFree

DS & A (Algorithm Analysis - Examples)

By

| CHAPTER 8 |

In our previous chapter, we discussed the different measures of Algorithm Complexity, namely Big-O, Big Omega and Big Theta. This chapter will be following after the concepts from the previous chapter(Measures of Algorithm Complexity). So, having basic knowledge about the different measures of Algorithm Complexity is a must for someone reading this chapter.

Pre-requisite:
Proper understanding of Running Time, Big-O, Big Omega, and Big Theta(If those terms are new to you, you can learn more about them here)
Big-O, Big Ω, and Big θ if Running time is known...

Example 1
Running Time, T(n) = 3n²

Big O
T(n) ≤ cf(n) {By definition of Big O}
3n² ≤ cf(n)

By substituting,
c = 3,     f(n) = n²,     n0 = 1
3n² = 3n²
O(f(n)) = O(n²)

Therefore, T(n) is in O(n²)

Big Ω
T(n) ≥ cf(n) {By definition of Big Ω}
3n² ≥ cf(n)

By substituting,
c = 3,     f(n) = n²,     n0 = 1
3n² = 3n²
Ω(f(n)) = Ω(n²)

Therefore, T(n) is in Ω(n²)

Big θ
Since T(n) is in O(n²) & T(n) is in Ω(n²)
Therefore, T(n) is in θ(n²)

Example 2
Running Time, T(n) = 3n² + n

Big O
T(n) ≤ cf(n) {By definition of Big O}
3n² + n ≤ 3n² + n² ⇒ 3n² + n ≤ 4n²

By substituting,
c = 4,     f(n) = n²,     n0 = 1
3n² + n ≤ 4n²
O(f(n)) = O(n²)

Therefore, T(n) is in O(n²)

Big Ω
T(n) ≥ cf(n) {By definition of Big Ω}
3n² + n ≥ 3n² + n² ⇒ 3n² + n ≤ 4n²

By substituting,
c = 4,     f(n) = n²,     n0 = 1
3n² + n ≥ 4n²
Ω(f(n)) = Ω(n²)

Therefore, T(n) is in Ω(n²)

Big θ
Since T(n) is in O(n²) & T(n) is in Ω(n²)
Therefore, T(n) is in θ(n²)

Big-O, Big Ω, and Big θ of a program...

Example 3
  1.  a = b;
  • Usually, time Complexity of an Assignment, Addition, and Subtraction operation are constant. So it is denoted by C. Therefore, Running Time, T(n) = C
  • Therefore, T(n) is in O(1), Ω(1) & θ(1)
Example 4
  1. //Part 1
  2. sum = 0;    -------------------- Statement 1

  4. //Part 2
  5. for (int i = 0; i <= n; i++)
  6. sum += n;   -------------------- Statement 2
  • Running Time, T(n) = Running Time of Part 1 + Running Time of Part 2
  • Running Time of Part 1 = Running Time of Statement 1 = C
  • Since "Part 2" has a for loop which executes n times. So, Statement 2 will be executed n times.
  • Running Time of Part 2 = (n * Running Time of Statement 2) = (n * C) = Cn
  • Running Time, T(n) = (C + Cn)
  • Therefore, the algorithm is in O(n), Ω(n) & θ(n)
Example 5
  1. value = 0;
  2. for (i = 1; i <= n; i++)
  3.     for (j = 1; j <= n; j++)
  4.     value = 2;              ---------------- Statement 1
  • Running Time, T(n) = n * n * T(Statement 1)
  • Running Time, T(n) = n * n * C
  • Running Time, T(n) = n² * C
  • Running Time, T(n) = Cn²
  • Therefore, the algorithm is in O(n²), Ω(n²) & θ(n²)
Example 6
  1. value = 0;
  2. if(value > 0)
  3. {
  4.   for (i = 1; i <= n; i++)
  5.     for (j = 1; j <= n; j++)
  6.       for (k = 1; k <= n; k++)
  7.       value = 2;              ---------------- Statement 1
  8. }
  9. else
  10. {
  11.   value++;                    ---------------- Statement 2
  12. }

Note : 
1) In case the program contains an "if-else" statement, consider the greater complexity of the then/else clause.
2) In case the program contains a "switch" statement, consider the most expensive case.
  • Since, if(value > 0){...} > else{...}
  • Therefore, Running Time, T(n) = n * n * n * T(Statement 1)
  • Running Time, T(n) = n * n * n * C
  • Running Time, T(n) = n³ * C
  • Running Time, T(n) = Cn³
  • Therefore, the algorithm is in O(n³), Ω(n³) & θ(n³)
Quiz 1
What is the Big-O if T(n) = C + Cn/2 + Cn² = Cnlog(n)?
 O(n)
 O(n²)
 O(n³)
 None of the Above


Quiz 2
  1. for (i = 1; i <= n; i++)
  2.     for (j = 1; j <= n; j++)
  3.          sum ++;
  4.     for (k = 1; k < n; k++)
  5.          A[k] = k;

What are the Big-O, Big Omega, and Big Theta of the program?
 O(n), Ω(n²), θ(n²)
 O(n²), Ω(n²), θ(n)
 O(n²), Ω(n²), θ(n²)
 None of the Above


Quiz 3
  1. sum1 = 0;
  2. for (i = 1; i <= n; i++)
  3.     for (j = 1; j <= n; j++)
  4.          sum1 ++;
  5. sum2 = 0;
  6. for (i = 1; i <= n; i++)
  7.     for (j = 1; j <= n; j++)
  8.          sum2 ++;

What are the Big-O, Big Omega, and Big Theta of the program?
 O(n²), Ω(n²), θ(n²)
 O(n²), Ω(n²), θ(n)
 O(n³), Ω(n²), θ(n²)
 O(n³), Ω(n²), θ(n³)

( If you like the content here, follow TSP on social media to get notified on future updates)


Comments

Post a Comment

Share on Social Media

Most Viewed Posts

DS & A (Algorithm Analysis - Best, Worst and Average Case)

By
Image
|  CHAPTER 5  | Note: If it's your first time visiting this website I strongly recommend you to read the previous chapter before reading this chapter. Till now we learned about what Data Structures and Algorithms are, some basic terminologies and a few  concepts  of Algorithm analysis.   And continuing our ongoing journey of Data Structures and Algorithms, today we will discuss the Best Case, Average Case and Worst Case of an algorithm. Algorithm Case Analysis In the last chapter, we learned that every algorithm has running time[T(n)] and a growth rate. But that's not the end of it, an algorithm's running time and growth rate are not the only factors that we should consider while designing an algorithm. For some algorithms, different inputs result in different running time. And that brings forth the necessity of the concept of Best, Average, and Worst Case of algorithms. Example Consider we have four boxes tagged 1,2,3 & 4, and the boxes con
Read more

SPACE & DRAGONS

By
Image
Space and Dragons is a top-down endless space shooter where the player takes on the role of a brave space warrior. In the game, the player has to fight against fierce Space Dragons while making the way through other obstacles such as space debris and much more. FEATURES: SPACE DRAGONS MOVING DEBRIS POWER-UPS HEALTH BOOST SHIELD AND much more SCREENSHOTS...... APPLICATIONS USED : QT Creator (A C++ based framework) GIMP (An Image Manipulation Software) AUDACITY (An Audio Manipulation Software) NOTE: The game resources have been collected from the OpenGameArt website and various other online sources. The used game assets are not my property. GAME DOWNLOAD LINK: DOWNLOAD GAME GAME REQUIREMENTS OS : WINDOWS RAM : 1 GB HARD DRIVE : 150 MB CONTROLS: LEFT, RIGHT keys for movements and SPACE to Shoot SPACE SHOOTER IN ACTION UPDATE << Click here to download the source code >> Zip Password: TheSuperProgrammer NOTE: The game
Read more

DS & A(Queue)

By
Image
|  CHAPTER 14  | In this chapter, our topic of discussion will be the "Queue" Data Structure. But, before we get started, I would recommend you to read the previous chapters on Data Structures & Algorithms  (especially the chapters on Array List , Linked List , Array Stack , and Linked Stack ), that is in case it's your first time visiting my blog. Queue: Just like Stacks, Queues also are a restricted version of List but with a few minor differences compared to Stack. The following are some of the notable characteristics of a Queue: Data can only be inserted from the rear/back. Data insertion is referred to as  ENQUEUE . Data can only be deleted from the front. Data deletion is referred to as  DEQUEUE . Alternatively,  ENQUEUE  and  DEQUEUE  should always be executed on the opposite ends of the Queue. A Queue follows the  FIFO (First In First Out)   principle. The first and the last elements are referred to as FRONT and REAR respectively.
Read more