tag:blogger.com,1999:blog-90681263678420468142023-11-16T02:34:58.757-08:00Java GreedyBlog dedicated to data structures & algorithms in JavaRahul Askarhttp://www.blogger.com/profile/10523230965873417240noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-9068126367842046814.post-11996521288391014662016-07-01T09:42:00.000-07:002016-07-01T09:51:23.160-07:00Binary Search In Java And It's Complexity<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: "verdana" , sans-serif;">Have you ever used a word dictionary of any language?? You must be thinking that what word dictionary has to do with binary search, right? Well, it has. Binary search is exactly similar to the searching for a word in a dictionary!!</span><br />
<div>
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div>
<span style="font-family: "verdana" , sans-serif;">By the way, binary search has one precondition- data structure needs to be present in sorted order. Like a dictionary has words arranged in sorted order. We can sort data structure using various sorting algorithms.</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;"><b>Steps to search for a word in a dictionary?</b></span></div>
<div>
<ol style="text-align: left;">
<li><span style="font-family: "verdana" , sans-serif;">Go to the middle of the dictionary.</span></li>
<li><span style="font-family: "verdana" , sans-serif;">If you find the word then stop here else go to step 3.</span></li>
<li><span style="font-family: "verdana" , sans-serif;">See if the word shall come after middle of the dictionary or before.</span></li>
<li><span style="font-family: "verdana" , sans-serif;">If it comes after the middle of the dictionary then take middle till end of the dictionary as a new dictionary & repeat steps 1-4.</span></li>
<li><span style="font-family: "verdana" , sans-serif;">If it comes before the middle of the dictionary then take middle till start of the dictionary as a new dictionary & repeat steps 1-4.</span></li>
<li><span style="font-family: "verdana" , sans-serif;">If you are at the extreme end or extreme start of the dictionary then it means the word you are looking for is not in the dictionary.</span></li>
</ol>
<div>
<span style="font-family: "verdana" , sans-serif;">Ok, it's time to code above logic in Java.</span><br />
<div style="background: #111111; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: scroll; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="color: silver; line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #008800; font-style: italic;">/**</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> * BINARY SEARCH JAVA PROGRAM</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> */</span>
<span style="color: #fb660a; font-weight: bold;">package</span> <span style="color: white;">javagreedy.</span><span style="color: #ff0086; font-weight: bold;">blogspot</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">com</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">import</span> <span style="color: white;">java.util.Arrays;</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">/**</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> * @author javagreedy.blogspot.com</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> * </span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> */</span>
<span style="color: #fb660a; font-weight: bold;">public</span> <span style="color: #fb660a; font-weight: bold;">class</span> <span style="color: white;">BinarySearchApp</span> <span style="color: white;">{</span>
<span style="color: #fb660a; font-weight: bold;">public</span> <span style="color: #fb660a; font-weight: bold;">static</span> <span style="color: #cdcaa9; font-weight: bold;">void</span> <span style="color: #ff0086; font-weight: bold;">main</span><span style="color: white;">(String[]</span> <span style="color: white;">args)</span> <span style="color: white;">{</span>
<span style="color: white;">String[]</span> <span style="color: white;">dictionary</span> <span style="color: white;">=</span> <span style="color: #fb660a; font-weight: bold;">new</span> <span style="color: white;">String[]{</span><span style="color: #0086d2;">"Dog"</span><span style="color: white;">,</span> <span style="color: #0086d2;">"Apple"</span><span style="color: white;">,</span> <span style="color: #0086d2;">"Ant"</span><span style="color: white;">,</span> <span style="color: #0086d2;">"Ball"</span><span style="color: white;">,</span>
<span style="color: #0086d2;">"Elephant"</span><span style="color: white;">,</span> <span style="color: #0086d2;">"Cat"</span><span style="color: white;">,</span> <span style="color: #0086d2;">"Frog"</span><span style="color: white;">,</span> <span style="color: #0086d2;">"Fish"</span><span style="color: white;">};</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// unsorted array of words</span>
<span style="color: white;">Arrays.</span><span style="color: #ff0086; font-weight: bold;">sort</span><span style="color: white;">(dictionary);</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// we have sorted it using existing sort api</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// provided by Java</span>
<span style="color: white;">System.</span><span style="color: #ff0086; font-weight: bold;">out</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">print</span><span style="color: white;">(</span><span style="color: #0086d2;">"Dictionary contains: "</span><span style="color: white;">);</span>
<span style="color: #fb660a; font-weight: bold;">for</span> <span style="color: white;">(String</span> <span style="color: white;">word</span> <span style="color: white;">:</span> <span style="color: white;">dictionary)</span> <span style="color: white;">{</span>
<span style="color: white;">System.</span><span style="color: #ff0086; font-weight: bold;">out</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">print</span><span style="color: white;">(word</span> <span style="color: white;">+</span> <span style="color: #0086d2;">" "</span><span style="color: white;">);</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// display the sorted dictionary</span>
<span style="color: white;">}</span>
<span style="color: white;">System.</span><span style="color: #ff0086; font-weight: bold;">out</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">println</span><span style="color: white;">();</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// line break</span>
<span style="color: white;">binarySearch(dictionary,</span> <span style="color: #0086d2;">"Ant"</span><span style="color: white;">);</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// binary search for Ant in dictionary</span>
<span style="color: white;">binarySearch(dictionary,</span> <span style="color: #0086d2;">"Tiger"</span><span style="color: white;">);</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// binary search for Tiger in</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// dictionary</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">private</span> <span style="color: #fb660a; font-weight: bold;">static</span> <span style="color: #cdcaa9; font-weight: bold;">void</span> <span style="color: #ff0086; font-weight: bold;">binarySearch</span><span style="color: white;">(String[]</span> <span style="color: white;">dictionary,</span> <span style="color: white;">String</span> <span style="color: white;">wordToFind)</span> <span style="color: white;">{</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">start</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// dictionary start</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">end</span> <span style="color: white;">=</span> <span style="color: white;">dictionary.</span><span style="color: #ff0086; font-weight: bold;">length</span> <span style="color: white;">-</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// dictionary end</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">middle</span> <span style="color: white;">=</span> <span style="color: white;">(start</span> <span style="color: white;">+</span> <span style="color: white;">end)</span> <span style="color: white;">/</span> <span style="color: #0086f7; font-weight: bold;">2</span><span style="color: white;">;</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// middle of the dictionary</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// base condition</span>
<span style="color: #fb660a; font-weight: bold;">while</span> <span style="color: white;">(start</span> <span style="color: white;"><=</span> <span style="color: white;">end)</span> <span style="color: white;">{</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// check if the word is at middle</span>
<span style="color: #fb660a; font-weight: bold;">if</span> <span style="color: white;">(dictionary[middle].</span><span style="color: #ff0086; font-weight: bold;">equals</span><span style="color: white;">(wordToFind))</span> <span style="color: white;">{</span>
<span style="color: white;">System.</span><span style="color: #ff0086; font-weight: bold;">out</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">println</span><span style="color: white;">(wordToFind</span> <span style="color: white;">+</span> <span style="color: #0086d2;">" is found at location "</span>
<span style="color: white;">+</span> <span style="color: white;">middle);</span>
<span style="color: #fb660a; font-weight: bold;">break</span><span style="color: white;">;</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// exit</span>
<span style="color: white;">}</span> <span style="color: #fb660a; font-weight: bold;">else</span> <span style="color: #fb660a; font-weight: bold;">if</span> <span style="color: white;">(dictionary[middle].</span><span style="color: #ff0086; font-weight: bold;">compareTo</span><span style="color: white;">(wordToFind)</span> <span style="color: white;"><</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">)</span> <span style="color: white;">{</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// check</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// if</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// wordTofind</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// is</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// after</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// middle</span>
<span style="color: white;">start</span> <span style="color: white;">=</span> <span style="color: white;">middle</span> <span style="color: white;">+</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// reset start</span>
<span style="color: white;">}</span> <span style="color: #fb660a; font-weight: bold;">else</span> <span style="color: white;">{</span>
<span style="color: white;">end</span> <span style="color: white;">=</span> <span style="color: white;">middle</span> <span style="color: white;">-</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// if wordTofind is before middle then reset</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// end</span>
<span style="color: white;">}</span>
<span style="color: white;">middle</span> <span style="color: white;">=</span> <span style="color: white;">(start</span> <span style="color: white;">+</span> <span style="color: white;">end)</span> <span style="color: white;">/</span> <span style="color: #0086f7; font-weight: bold;">2</span><span style="color: white;">;</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">// find middle of new dictionary</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">if</span> <span style="color: white;">(start</span> <span style="color: white;">></span> <span style="color: white;">end)</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// unexpected condition</span>
<span style="color: white;">System.</span><span style="color: #ff0086; font-weight: bold;">out</span>
<span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">println</span><span style="color: white;">(wordToFind</span> <span style="color: white;">+</span> <span style="color: #0086d2;">" is not present in the dictionary"</span><span style="color: white;">);</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
</pre>
</td></tr>
</tbody></table>
</div>
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">Output:</span><br />
<div style="background: #f0f0f0; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;">1
2
3</pre>
</td><td><pre style="line-height: 125%; margin: 0;">Dictionary <span style="color: #002070; font-weight: bold;">contains:</span> Ant Apple Ball Cat Dog Elephant Fish Frog
Ant is found at location <span style="color: #40a070;">0</span>
Tiger is not present in the dictionary
</pre>
</td></tr>
</tbody></table>
</div>
<span style="font-family: "verdana" , sans-serif;"><br /></span><span style="font-family: "verdana" , sans-serif;">Well, Java already provides a method for <i>binarySearch</i> in class <i>java.util.</i><b style="font-style: italic;">Arrays</b>. You can use it as below-</span><br />
<div style="background: #111111; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="color: silver; line-height: 125%; margin: 0;"></pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">index</span> <span style="color: white;">=</span> <span style="color: white;">Arrays.</span><span style="color: #ff0086; font-weight: bold;">binarySearch</span><span style="color: white;">(dictionary,</span><span style="color: #0086d2;">"Ant"</span><span style="color: white;">);</span>
</pre>
</td></tr>
</tbody></table>
</div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><b><br /></b></span></span>
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><b>What is the time complexity of binary search?</b></span></span></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><b>Worst Case:</b> Worst case will be when the element we are searching for is not present in the data structure. In the second execution of above program where we searched for "Tiger". Each time we divided dictionary into half. We went on doing this until there were no further division possible. If you see this looks similar to the <a href="https://javagreedy.blogspot.in/2016/06/finding-time-complexity-asymptotic.html#logarithmic" target="_blank">logarithmic time complexity</a>. Suppose we have 8 words then we will divide dictionary in the following ways- </span></span></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;">1. middle = 8/2 = 4</span></span></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;">2. middle = 4/2 = 2</span></span></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;">3. middle = 2/2 = 1 No further division is possible.</span></span></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;">Here, we divided dictionary 3 times. Mathematically: log(8) = 3 where log base is 2 as we are dividing dictionary each time by 2. So, if we have n elements in data structure then worst case complexity for binary search would be log(n).</span></span></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<br /></div>
<div class="MsoNormal" style="background-color: white; font-family: Verdana, Geneva, sans-serif; font-size: 15.84px; line-height: 22.176px;">
<span lang="EN-US" style="font-family: "verdana" , sans-serif; font-size: 15.84px; line-height: 22.176px;"><b>Best Case:</b> At the very first execution, we directly searched for the word in middle of the dictionary. And if that is the word we are looking for then this is the best case. </span><span lang="EN-US" style="font-family: "verdana" , sans-serif; font-size: 15.84px; line-height: 22.176px;">Irrespective of the number of words in a dictionary we will always have to check to divide the dictionary only once if it's the best case. So, best case complexity becomes O(1).</span></div>
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
</div>
</div>
Rahul Askarhttp://www.blogger.com/profile/10523230965873417240noreply@blogger.com0tag:blogger.com,1999:blog-9068126367842046814.post-48204403145312830292016-06-25T22:57:00.000-07:002016-06-26T10:01:29.798-07:00Linear Search In Java And It's Complexity<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;">As name says , linear search is searching
for an element in the data structure in a linear or sequential fashion. Suppose
I have a bag containing 20 balls which are having any random numbers from 1 to
100 printed on them. Then, how I can find the ball with number, say 55? If we use linear search then we will take
out one ball at a time and check a number on it till we find the one with
number 55.</span></span></div>
<div class="MsoNormal">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;">Let’s implement linear search in java-</span></span></div>
<div class="MsoNormal">
<br /></div>
<div style="background: #111111; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: scroll; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="color: grey; line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #008800; font-style: italic;">/**</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> * LINEAR SEARCH JAVA PROGRAM</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> */</span>
<span style="color: #fb660a; font-weight: bold;">package</span> <span style="color: white;">javagreedy.</span><span style="color: #ff0086; font-weight: bold;">blogspot</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">com</span><span style="color: white;">;</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">/**</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> * @author javagreedy.blogspot.com</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> *</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> */</span>
<span style="color: #fb660a; font-weight: bold;">public</span> <span style="color: #fb660a; font-weight: bold;">class</span> <span style="color: white;">LinearSearchApp</span> <span style="color: white;">{</span>
<span style="color: #fb660a; font-weight: bold;">public</span> <span style="color: #fb660a; font-weight: bold;">static</span> <span style="color: #cdcaa9; font-weight: bold;">void</span> <span style="color: #ff0086; font-weight: bold;">main</span><span style="color: white;">(String[]</span> <span style="color: white;">args)</span> <span style="color: white;">{</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">[]</span> <span style="color: white;">bag</span> <span style="color: white;">=</span> <span style="color: #fb660a; font-weight: bold;">new</span> <span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">[]</span> <span style="color: white;">{</span> <span style="color: #0086f7; font-weight: bold;">10</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">33</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">23</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">75</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">98</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">22</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">44</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">37</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">55</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">67</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">13</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">64</span><span style="color: white;">,</span>
<span style="color: #0086f7; font-weight: bold;">80</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">36</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">74</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">68</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">12</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">92</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">15</span><span style="color: white;">,</span> <span style="color: #0086f7; font-weight: bold;">20</span> <span style="color: white;">};</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// bag containing 20 numbers</span>
<span style="color: white;">linearSearch(bag,</span> <span style="color: #0086f7; font-weight: bold;">55</span><span style="color: white;">);</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// search 55 in bag</span>
<span style="color: white;">linearSearch(bag,</span> <span style="color: #0086f7; font-weight: bold;">29</span><span style="color: white;">);</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// search 29 in bag</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">private</span> <span style="color: #fb660a; font-weight: bold;">static</span> <span style="color: #cdcaa9; font-weight: bold;">void</span> <span style="color: #ff0086; font-weight: bold;">linearSearch</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">[]</span> <span style="color: white;">bag,</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">numToFind)</span> <span style="color: white;">{</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// scan complete bag</span>
<span style="color: #fb660a; font-weight: bold;">for</span> <span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">bag.</span><span style="color: #ff0086; font-weight: bold;">length</span><span style="color: white;">;</span> <span style="color: white;">i++)</span> <span style="color: white;">{</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// check element one by one</span>
<span style="color: #fb660a; font-weight: bold;">if</span> <span style="color: white;">(bag[i]</span> <span style="color: white;">==</span> <span style="color: white;">numToFind)</span> <span style="color: white;">{</span>
<span style="color: white;">System.</span><span style="color: #ff0086; font-weight: bold;">out</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">println</span><span style="color: white;">(</span><span style="color: #0086d2;">"Bingo!! "</span> <span style="color: white;">+</span> <span style="color: white;">numToFind</span>
<span style="color: white;">+</span> <span style="color: #0086d2;">" is found at location "</span> <span style="color: white;">+</span> <span style="color: white;">i);</span>
<span style="color: #fb660a; font-weight: bold;">return</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: white;">System.</span><span style="color: #ff0086; font-weight: bold;">out</span><span style="color: white;">.</span><span style="color: #ff0086; font-weight: bold;">println</span><span style="color: white;">(</span><span style="color: #0086d2;">"Oops! Bag doesn't contain "</span> <span style="color: white;">+</span> <span style="color: white;">numToFind</span>
<span style="color: white;">+</span> <span style="color: #0086d2;">" at all!"</span><span style="color: white;">);</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
</pre>
</td></tr>
</tbody></table>
</div>
<div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<br /></div>
<div style="background: #f0f0f0; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #002070; font-weight: bold;">Output:</span>
Bingo<span style="color: #666666;">!!</span> <span style="color: #40a070;">55</span> is found at location <span style="color: #40a070;">8</span>
Oops<span style="color: #666666;">!</span> Bag doesn't contain <span style="color: #40a070;">29</span> at all<span style="color: #666666;">!</span>
</pre>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><b>What is the time complexity of linearsearch?</b></span></span></div>
<div class="MsoNormal">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><b>Worst
Case:</b> See the second execution of
above program where we searched for number, 29 till last element in array and
we didn’t find it. This is the worst case when number is not present in the
array. For 20 array elements we checked
(line number 27) 20 times. So, if we have ‘n’ number of elements in bag then we
will have to check for ‘n’ times. So, worst case complexity will be O(n).</span></span></div>
<div class="MsoNormal">
<span lang="EN-US"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<span lang="EN-US" style="font-family: "verdana" , sans-serif;"><b>Best Case:</b> What if we found the number on
the first check itself?</span><span lang="EN-US" style="font-family: "verdana" , sans-serif;"> Well, you guessed it right; it’s the best case for linear search.
Irrespective of the number of elements in an array we will always have to check
for a number only once if it's the best case. So, best case complexity
becomes O(1).</span></div>
Rahul Askarhttp://www.blogger.com/profile/10523230965873417240noreply@blogger.com0tag:blogger.com,1999:blog-9068126367842046814.post-23105030369132691872016-06-04T06:32:00.000-07:002016-06-20T10:28:10.286-07:00Finding Time Complexity (Asymptotic Analysis)<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: "verdana" , sans-serif;">There are some basic code statements that are used to build complete program. It is necessary to know their time complexities in order to calculate the time complexity of whole code/algorithm.</span><br />
<span style="font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">We will look at them one by one-</span></span><br />
<span style="font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;"><b><a name="constanttime">1. Constant Time [O(1)]</a></b></span></span><br />
<div style="color: black; font-family: monospace; font-size: 16px; height: auto; line-height: 20px; padding: 0px; text-align: left; width: 99%;">
<pre style="background-color: #e5ebe8; border: 1px solid #ddd; float: left; margin-top: 0; padding-left: 5px; padding-right: 5px; text-align: center; width: auto;">1
2
3
4
5
6
</pre>
<pre style="background: url("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx7bD0GrWB8xrNm3AxuUvryUn-S-yC4oeiBmZtMTABVxLvTZm3MVSr19ritCMc_FG6I6Z14lKWeAjJFAfBOJbWCx1hpPF8knRbpdRZJL702aeWz53KavPm3HCsM-8BIvvXfY1CjoVwev8/w1-h40-no/bg-code.jpg") top left #fdfdfd; border: 1px solid #ddd; display: block; margin-bottom: 0; margin-top: 0; overflow: auto; padding-left: 8px; white-space: pre; width: auto; word-wrap: normal;">void sum() {
int a= 2;
int b=3;
int c = a + b;
System.out.println(c);
}</pre>
</div>
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">In above code we are not taking any input. So this code is independent of input size. Lets say the above code takes time C to execute. This time will always be constant irrespective of the input size. In asymptotic analysis we say that the time complexity is O(1).</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<b style="font-family: Verdana, sans-serif;"><span style="font-family: "verdana" , sans-serif;"><a name="simpleloops">2. Simple Loops</a></span></b><br />
<div style="color: black; font-family: monospace; font-size: 16px; height: auto; line-height: 20px; padding: 0px; text-align: left; width: 99%;">
<pre style="background-color: #e5ebe8; border: 1px solid #ddd; float: left; margin-top: 0; padding-left: 5px; padding-right: 5px; text-align: center; width: auto;">1
2
3
4
5
6
</pre>
<pre style="background: url("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx7bD0GrWB8xrNm3AxuUvryUn-S-yC4oeiBmZtMTABVxLvTZm3MVSr19ritCMc_FG6I6Z14lKWeAjJFAfBOJbWCx1hpPF8knRbpdRZJL702aeWz53KavPm3HCsM-8BIvvXfY1CjoVwev8/w1-h40-no/bg-code.jpg") top left #fdfdfd; border: 1px solid #ddd; display: block; margin-bottom: 0; margin-top: 0; overflow: auto; padding-left: 8px; white-space: pre; width: auto; word-wrap: normal;">int k= 0;//time c1
// loop will execute n times
for(int i = 1 ; i<=n ; i++)
{
k= k+ i; //time C2
}</pre>
</div>
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">Total time = Time taken by initialization statement + Time taken by statements inside loop x Number of time loop will execute</span><br />
<span style="font-family: "verdana" , sans-serif;">Total time = C1 + C2 x n</span><br />
<span style="font-family: "verdana" , sans-serif;">Total time = C1 + C2n </span><span style="font-family: "verdana" , sans-serif;">i.e. O(n)</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<b style="font-family: Verdana, sans-serif;"><span style="font-family: "verdana" , sans-serif;"><a name="nestedloops">3. Nested Loops</a></span></b><br />
<div style="color: black; font-family: monospace; font-size: 16px; height: auto; line-height: 20px; padding: 0px; text-align: left; width: 99%;">
<pre style="background-color: #e5ebe8; border: 1px solid #ddd; float: left; margin-top: 0; padding-left: 5px; padding-right: 5px; text-align: center; width: auto;">1
2
3
4
5
6
7
8
9
10
11
12
13
14
</pre>
<pre style="background: url("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx7bD0GrWB8xrNm3AxuUvryUn-S-yC4oeiBmZtMTABVxLvTZm3MVSr19ritCMc_FG6I6Z14lKWeAjJFAfBOJbWCx1hpPF8knRbpdRZJL702aeWz53KavPm3HCsM-8BIvvXfY1CjoVwev8/w1-h40-no/bg-code.jpg") top left #fdfdfd; border: 1px solid #ddd; display: block; margin-bottom: 0; margin-top: 0; overflow: auto; padding-left: 8px; white-space: pre; width: auto; word-wrap: normal;">int k= 0, m = n; //time C1
// outer loop will execute n times
for(int i = 1 ; i<=n ; i++) {
k= k+ i; //time C2
// inner loop will also execute n times
for(int j = n ; j>=1 ; j--) {
m= m- j; //time C3
}
}
</pre>
</div>
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">In nested loops we analyze time from inside out. </span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">Time taken by inner loop = C3 x n</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">Total time = Time taken by initialization statement + Time taken by statements inside outer loop x Number of time outer loop will execute</span><br />
<span style="font-family: "verdana" , sans-serif;">Total time = C1 + (C2 + C3n) x n</span><br />
<span style="font-family: "verdana" , sans-serif;">Total time = C1 + C2n + C3<span style="font-size: 12pt; line-height: 115%;">n</span><sup style="line-height: 115%;">2 </sup>time i.e. O(<span style="font-size: 12pt; line-height: 18.4px;">n</span><sup style="line-height: 15.3333px;">2</sup>) </span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<b style="font-family: Verdana, sans-serif;"><span style="font-family: "verdana" , sans-serif;"><a name="consecutive">4. Consecutive Statements</a></span></b><br />
<div style="color: black; font-family: monospace; font-size: 16px; height: auto; line-height: 20px; padding: 0px; text-align: left; width: 99%;">
<pre style="background-color: #e5ebe8; border: 1px solid #ddd; float: left; margin-top: 0; padding-left: 5px; padding-right: 5px; text-align: center; width: auto;">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
</pre>
<pre style="background: url("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx7bD0GrWB8xrNm3AxuUvryUn-S-yC4oeiBmZtMTABVxLvTZm3MVSr19ritCMc_FG6I6Z14lKWeAjJFAfBOJbWCx1hpPF8knRbpdRZJL702aeWz53KavPm3HCsM-8BIvvXfY1CjoVwev8/w1-h40-no/bg-code.jpg") top left #fdfdfd; border: 1px solid #ddd; display: block; margin-bottom: 0; margin-top: 0; overflow: auto; padding-left: 8px; white-space: pre; width: auto; word-wrap: normal;">int x = 0, k=0; //time C1
// loop will execute n times
for(int y = 1 ; y<=n ; y++) {
x= x+ y; //time C2
}
// outer loop will execute n times
for(int i = 1 ; i<=n ; i++) {
k= k+ i; //time C3
// inner loop will also execute n times
for(int j = n ; j>=1 ; j--) {
m= m- j; //time C4
}
}</pre>
</div>
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">Total time = C1 + C2n + (C3 + C4n) x n</span><br />
<span style="font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;">Total time = C1 + C2n + C3n + C4</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;">n</span><span lang="EN-US" style="background-color: white; font-size: 12pt; line-height: 18.4px;"><sup>2 </sup></span></span><br />
<span style="font-family: "verdana" , sans-serif;">i.e. O(</span><span style="font-family: "verdana" , sans-serif; font-size: 12pt; line-height: 18.4px;">n</span><sup style="font-family: verdana, sans-serif; line-height: 15.3333px;">2</sup><span style="font-family: "verdana" , sans-serif;">) </span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-weight: bold;"><span style="font-family: "verdana" , sans-serif;"><a name="ifelse">5. If else statements</a></span></span><br />
<div style="color: black; font-family: monospace; font-size: 16px; height: auto; line-height: 20px; padding: 0px; text-align: left; width: 99%;">
<pre style="background-color: #e5ebe8; border: 1px solid #ddd; float: left; margin-top: 0; padding-left: 5px; padding-right: 5px; text-align: center; width: auto;">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
</pre>
<pre style="background: url("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx7bD0GrWB8xrNm3AxuUvryUn-S-yC4oeiBmZtMTABVxLvTZm3MVSr19ritCMc_FG6I6Z14lKWeAjJFAfBOJbWCx1hpPF8knRbpdRZJL702aeWz53KavPm3HCsM-8BIvvXfY1CjoVwev8/w1-h40-no/bg-code.jpg") top left #fdfdfd; border: 1px solid #ddd; display: block; margin-bottom: 0; margin-top: 0; overflow: auto; padding-left: 8px; white-space: pre; width: auto; word-wrap: normal;">boolean bool; //time C1
if(bool) {
return true; //time C2
}
else {
// loop will execute n times
for(int y = 1 ; y<=n ; y++) {
y++; //time C3
}
}</pre>
</div>
<span lang="EN-US" style="background-color: white; font-size: 12pt; line-height: 18.4px;"><sup><span style="font-family: "verdana" , sans-serif;"><br /></span></sup></span>
<span style="font-family: "verdana" , sans-serif;">Here we check for worst case scenario <br />(remember <a href="https://javagreedy.blogspot.in/2016/06/asymptotic-notations-big-omega-notation.html#generalrules" target="_blank">general rules</a>? ) i.e. what will be the larger time complexity?</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">Total time will be either C1 + C2 in case 'if' condition is true. Or it will be C3n in case else statement executes. So, maximum time complexity in worst case would be O(n).</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-weight: bold;"><span style="font-family: "verdana" , sans-serif;"><a name="logarithmic">6. Logarithmic</a></span></span><br />
<div style="color: black; font-family: monospace; font-size: 16px; height: auto; line-height: 20px; padding: 0px; text-align: left; width: 99%;">
<pre style="background-color: #e5ebe8; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 1px solid rgb(221, 221, 221); float: left; font-size: 16px; margin-top: 0px; padding-left: 5px; padding-right: 5px; text-align: center; width: auto;">1
2
3
4
5
</pre>
<pre style="background-attachment: initial; background-clip: initial; background-color: #fdfdfd; background-image: url("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhx7bD0GrWB8xrNm3AxuUvryUn-S-yC4oeiBmZtMTABVxLvTZm3MVSr19ritCMc_FG6I6Z14lKWeAjJFAfBOJbWCx1hpPF8knRbpdRZJL702aeWz53KavPm3HCsM-8BIvvXfY1CjoVwev8/w1-h40-no/bg-code.jpg"); background-origin: initial; background-position: 0% 0%; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 1px solid rgb(221, 221, 221); display: block; margin-bottom: 0px; margin-top: 0px; overflow: auto; padding-left: 8px; white-space: pre; width: auto; word-wrap: normal;"> for(int i = 1 ; i<=n ; i++) <span style="font-size: 16px;">{
i= i*2; //time C
}</span></pre>
</div>
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">Here value of i is becoming twice in every execution and hence reducing the number of times the loop will execute. Let's see how it goes-</span><br />
<span style="font-family: "verdana" , sans-serif;">Initially i = 1 i.e. 2<span lang="EN-US" style="background-color: white; font-size: 12pt; line-height: 18.4px;"><sup>0</sup></span></span><br />
<span style="font-family: "verdana" , sans-serif;">Execution 1 -> i = 2 i.e. 2<span lang="EN-US" style="background-color: white; font-size: 12pt; line-height: 18.4px;"><sup>1</sup></span></span><br />
<span style="font-family: "verdana" , sans-serif;">Execution 2 -> i = 4 i.e. 2<span lang="EN-US" style="background-color: white; font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span></span><br />
<div style="margin-bottom: .0001pt; margin: 0cm;">
<span style="background: white; font-family: "verdana" , sans-serif;">Execution 3 -> i = 8 i.e. 2<sup>3</sup></span></div>
<div style="margin-bottom: .0001pt; margin: 0cm;">
<span style="background-color: white; font-family: "verdana" , sans-serif;">Execution 4 -> i = 16 i.e. 2</span><sup style="font-family: Verdana, sans-serif;">4 </sup><span style="background-color: white; font-family: "verdana" , sans-serif;">and so
on...</span></div>
<div style="margin: 0cm 0cm 0.0001pt;">
<o:p></o:p></div>
<span style="background-color: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span>
<span style="font-family: "verdana" , sans-serif;"><span style="background-color: white;">Lets say </span><span style="background-color: white;">2</span><span lang="EN-US" style="background-color: white; font-size: 12pt; line-height: 18.4px;"><sup>k </sup></span><span style="background-color: white;">= n. If we take log on both side to the base 2, we get</span></span><br />
<span style="font-family: "verdana" , sans-serif;"><span style="background-color: white;">log</span><span style="background-color: white;">2</span><span lang="EN-US" style="background-color: white; font-size: 12pt; line-height: 18.4px;"><sup>k</sup></span><span style="background-color: white;"> = logn</span></span><br />
<span style="background-color: white;"><span style="font-family: "verdana" , sans-serif;">k.log2 = logn</span></span><br />
<span style="background-color: white;"><span style="font-family: "verdana" , sans-serif;">k = logn (since log2 to the base 2 is 1)</span></span><br />
<span style="background-color: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span>
<span style="background-color: white;"><span style="font-family: "verdana" , sans-serif;">k is nothing but the total time taken by loop and hence time complexity is O(logn).</span></span><br />
<div>
<span style="font-family: "verdana" , sans-serif; font-weight: bold;"><br /></span></div>
</div>
Rahul Askarhttp://www.blogger.com/profile/10523230965873417240noreply@blogger.com0tag:blogger.com,1999:blog-9068126367842046814.post-34873031111794492922016-06-01T02:00:00.000-07:002016-06-18T00:48:36.715-07:00Asymptotic Notations- Big Omega Notation [Ω] & Big Theta Notation [Ѳ]<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;">In the previous post we have seen the </span><span style="font-family: "verdana" , sans-serif; font-weight: bold;">1. <a href="http://javagreedy.blogspot.in/2016/05/asymptotic-analysis-big-o-notation.html#bigo" target="_blank">Big O Notation [O]</a></span><span style="font-family: "verdana" , sans-serif;">. Next is-</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<b style="font-family: Verdana, sans-serif;"><a name="bigomega">2. Big Omega Notation [Ω]</a></b></div>
<br />
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;">In opposite to the big O notation this notation represents tightest lower bound of the given function.</span><br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJNy-vi2OwC3bPsIH2eBiTxrVvKLffzCSLYY3D_UNdsm0tYtsGWdRUhkaVR4yR9IwbEkTUr03hqAoMpplG68URBuqL13R97SMYDKv6W0HTK1IBaVnpPgiJO6MTxUyR1DueVfGDSXaBFjw/s1600/Omega.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img alt="Big Omega" border="0" height="285" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJNy-vi2OwC3bPsIH2eBiTxrVvKLffzCSLYY3D_UNdsm0tYtsGWdRUhkaVR4yR9IwbEkTUr03hqAoMpplG68URBuqL13R97SMYDKv6W0HTK1IBaVnpPgiJO6MTxUyR1DueVfGDSXaBFjw/s320/Omega.jpg" title="Big Omega" width="320" /></a></div>
<span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;">Analytically we say as: f(n) belongs to Ω(g(n)) </span><span lang="EN-US" style="background: white;">as there exists<span class="apple-converted-space"> </span><i>c</i> > 0 (e.g.,<span class="apple-converted-space"> </span><i>c</i> = 1) and<span class="apple-converted-space"> <i>n</i></span>0 (e.g.<span class="apple-converted-space"> <i>n</i></span>0 = 5) such that<span class="apple-converted-space"> </span></span><i style="font-family: Verdana, sans-serif;"><span lang="EN-US" style="background: white;">f</span></i><span lang="EN-US" style="background: white;">(<i>n</i>)</span><span lang="EN-US" style="background: white;"> </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;">≥ </span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"><i>c.</i></span><i style="font-family: Verdana, sans-serif;"><span lang="EN-US" style="background: white;">g</span></i><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">(<i>n</i>)</span><span class="apple-converted-space" style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;"> </span></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">whenever<span class="apple-converted-space"> <i>n</i></span> ≥ <i>n</i>0.</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">Example- l</span></span><span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">ets find tightest lower bound of f(n) = 5n</span></span><span lang="EN-US" style="font-size: 12pt; line-height: 115%;"><sup>2</sup>+</span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif; font-size: 12pt; line-height: 115%;">2n+1.</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif; font-size: 12pt; line-height: 115%;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;">By looking to f(n) we can say that if we have a function g(n) = <span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>2 </sup></span>(As, </span></span><span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-size: 12pt; line-height: 18.4px;"><sup>2 </sup></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">is always less than 5</span><span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">) then it will be the tightest lower bound of f(n). </span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">In other words: <i>f</i></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">(n)</span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"> ≥ <i>c.</i></span><i style="font-family: verdana, sans-serif;"><span lang="EN-US" style="background: white;">g</span></i><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">(n)</span><span class="apple-converted-space" style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;"> </span></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">for c=1 & n0=1. In Big Omega, we say f(n) = Ω(<span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span>) & it is read as </span><i style="font-family: verdana, sans-serif;"><b>"f of n is big omega of <span lang="EN-US" style="font-family: "times new roman"; font-style: normal;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; font-style: normal; line-height: 18.4px;"><sup>2</sup></span>"</b></i><span style="font-family: "verdana" , sans-serif;">.</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><span style="background-color: white;">Another thing to note is if f(n) </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;">= Ω(</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span><span style="background-color: white; font-family: "verdana" , sans-serif;">) then </span><span style="font-family: "verdana" , sans-serif;"><span style="background-color: white;">f(n) </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;">= Ω(</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span style="background-color: white; font-family: "verdana" , sans-serif;">) or </span><span style="font-family: "verdana" , sans-serif;"><span style="background-color: white;">f(n) </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;">= Ω(logn</span><span style="background-color: white; font-family: "verdana" , sans-serif;">) because n & logn are lesser than </span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;">But since we use Big Omega notation to represent <u>tightest lower bound</u> of the function, we will say <span style="font-family: "verdana" , sans-serif;">f(n) </span>= Ω(<span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span>) instead of Ω(n) or Ω(logn).</span><span style="font-family: "arial" , sans-serif;"><o:p></o:p></span></span><br />
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;">Big Omega notation is usually used to specify time/space complexity of the given algorithm in <b>best case </b>scenario. </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;"><a name="bestcase">Best case scenario is the situation when algorithm takes the least time to run or the least memory during it's execution.</a></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b style="font-family: Verdana, sans-serif;"><a name="bigtheta">3. Big Theta Notation [Ѳ]</a></b><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;">This notation is used to find average time/space complexity of an algorithm.</span><br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfvx98OfDB4WsRddKiV3rc9FbXJwJB0_xu5OHLLv7JIt8Mf9-2UyMP8cODgAHfWJ1rXjLCphtePaOHDppy5PCdjUkFHD93WA0drcuk6SN-pZN2js5GSi-mEvnQSixewPG8hE0p7ljit98/s1600/Theta.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img alt="Big Theta" border="0" height="285" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfvx98OfDB4WsRddKiV3rc9FbXJwJB0_xu5OHLLv7JIt8Mf9-2UyMP8cODgAHfWJ1rXjLCphtePaOHDppy5PCdjUkFHD93WA0drcuk6SN-pZN2js5GSi-mEvnQSixewPG8hE0p7ljit98/s320/Theta.jpg" title="Big Theta" width="320" /></a></div>
<span style="font-family: "verdana" , sans-serif;">Average complexity will always be between tightest upper bound and tightest lower bound.</span></div>
<div class="MsoNormal">
</div>
<br />
<div style="color: black; font-size: medium; font-variant: normal; letter-spacing: normal; line-height: normal; margin: 0px; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">
<div style="font-family: 'times new roman';">
<span style="font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-style: normal;">Analytically we say as: f(n) belongs to <span style="font-family: "verdana" , sans-serif;">Ѳ</span>(g(n)) </span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-weight: normal;">as there exists<span class="apple-converted-space" style="font-style: normal;"> </span><i style="font-style: normal;">c</i> > 0, <i>d</i></span></span></span><span style="background-color: white; font-family: "verdana" , sans-serif; font-style: normal;"> > 0</span><span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"> (e.g.,<span class="apple-converted-space" style="font-style: normal;"> </span><i style="font-style: normal;">c</i> = 1, d=3) and<span class="apple-converted-space" style="font-style: normal;"> <i>n</i></span>0 (e.g.<span class="apple-converted-space" style="font-style: normal;"> <i>n</i></span>0 = 5) such that<span class="apple-converted-space"> c.<i>g</i></span></span></span><span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;">(<i>n</i>)</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"> </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;">≥ </span><span style="font-family: "verdana" , sans-serif;"><i style="font-family: Verdana, sans-serif;"><span lang="EN-US" style="background: white;">f</span></i><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;">(<i>n</i>)</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial;"> </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;">≥ </span><span style="background-color: white; font-family: "verdana" , sans-serif;"><i>d.</i></span><span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;">g</span></span><span lang="EN-US" style="background-color: white; font-family: "verdana" , sans-serif;">(<i>n</i>)</span><span class="apple-converted-space" style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;"> </span></span><span lang="EN-US" style="background-color: white; font-family: "verdana" , sans-serif;">whenever<span class="apple-converted-space"> <i>n</i></span> ≥ <i>n</i>0.</span></div>
<div style="font-family: 'times new roman';">
<span lang="EN-US" style="background-color: white; font-family: "verdana" , sans-serif;"><br /></span></div>
<span style="font-family: "verdana" , sans-serif;"><span style="background-color: white;">Example- suppose, we have a function f(n) = 7</span></span><span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-size: 12pt; line-height: 18.4px;"><sup>3</sup>+</span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif; font-size: 12pt; line-height: 18.4px;">2.</span><br />
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif; font-size: 12pt; line-height: 18.4px;">Then f(n) = O(<span lang="EN-US" style="font-family: "times new roman"; font-size: small; line-height: normal;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>3</sup></span>) for c = 8, n0=2. Also, f(n) = </span><span style="background-color: white; font-family: "verdana" , sans-serif;">Ω(</span><span lang="EN-US" style="background-color: white; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="background-color: white; font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>3</sup></span><span style="background-color: white; font-family: "verdana" , sans-serif;">) for c = 6, n0=2. Now as lower & upper bound of f(n) is </span><span lang="EN-US" style="background-color: white; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="background-color: white; font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>3</sup></span><span style="background-color: white; font-family: "verdana" , sans-serif;"> then we can say average of time complexity for f(n) is </span><span lang="EN-US" style="background-color: white; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="background-color: white; font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>3</sup></span><span style="background-color: white; font-family: "verdana" , sans-serif;">.</span><span style="background-color: white; font-family: "verdana" , sans-serif;"> Hence, f(n) = </span><span style="background-color: white; font-family: "verdana" , sans-serif;">Ѳ</span><span style="background-color: white; font-family: "verdana" , sans-serif;">(</span><span lang="EN-US" style="background-color: white; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="background-color: white; font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>3</sup></span><span style="background-color: white; font-family: "verdana" , sans-serif;">) </span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">& it is read as </span><i style="font-family: verdana, sans-serif;"><b>"f of n is big theta of <span lang="EN-US" style="background-color: white; font-family: "times new roman"; font-style: normal;"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="background-color: white; font-family: "times new roman"; font-size: 12pt; font-style: normal; line-height: 18.4px;"><sup>3</sup></span>"</b></i><span style="font-family: "verdana" , sans-serif;">.</span><br />
<span style="font-family: "verdana" , sans-serif;"><br /></span>
<span style="font-family: "verdana" , sans-serif;"><b><a name="generalrules">General rules while analyzing time complexity:</a></b></span><br />
<span style="font-family: "verdana" , sans-serif;">1. We analyze the time complexity for very large input size.</span><br />
<span style="font-family: "verdana" , sans-serif;">2. We consider worst case scenario i.e. Big O notation.</span><br />
<span style="font-family: "verdana" , sans-serif;">3. For any function, f(n) then we drop lower order terms & constant multipliers.</span><br />
<span style="font-family: "verdana" , sans-serif;">e.g. f(n) </span><span style="font-family: "verdana" , sans-serif;">= 10</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>4</sup></span><span style="font-family: "verdana" , sans-serif;">+</span><span style="font-family: "verdana" , sans-serif;">4</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>3</sup></span><span style="font-family: "verdana" , sans-serif;">+</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span><span style="font-family: "verdana" , sans-serif;">+2</span><span style="font-family: "verdana" , sans-serif;">n+5 then f(</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span style="font-family: "verdana" , sans-serif;">) = O(</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>4</sup></span><span style="font-family: "verdana" , sans-serif;">)</span><br />
<span style="font-family: "verdana" , sans-serif;">Here, we have dropped lower order terms which are </span><span style="font-family: "verdana" , sans-serif;">4</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>3</sup></span><span style="font-family: "verdana" , sans-serif;">,</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>2</sup></span><span style="font-family: "verdana" , sans-serif;">,2</span><span style="font-family: "verdana" , sans-serif;">n & 5. We have considered </span><span style="font-family: "verdana" , sans-serif;">10</span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>4 </sup></span><span style="font-family: "verdana" , sans-serif;">and finally we omitted </span><span style="font-family: "verdana" , sans-serif;">10, which is a constant multiplier & we are left with </span><span lang="EN-US" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; font-family: "times new roman";"><span style="font-family: "verdana" , sans-serif;">n</span></span><span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup>4.</sup></span><br />
<span style="font-family: "verdana" , sans-serif;"></span><br />
<span lang="EN-US" style="font-family: "times new roman"; font-size: 12pt; line-height: 18.4px;"><sup></sup></span></div>
</div>
Rahul Askarhttp://www.blogger.com/profile/10523230965873417240noreply@blogger.com0tag:blogger.com,1999:blog-9068126367842046814.post-35511432561178261132016-05-26T08:11:00.003-07:002016-06-18T00:49:27.630-07:00Asymptotic Notations- Big O Notation [O]<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;">We always hear below common terms in the world of computer science: </span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><a name="ds"><b>Data Structure-</b></a> It defines how the data is arranged in computer’s memory. For example- arrays, stacks , linked lists are few of the popular data structures. </span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><a name="algo"><b>Algorithm-</b></a> It is a set of instructions used to manipulate data structures. For example- sorting algorithm, searching algorithm etc.</span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><a name="timecomplexity"><b>Time Complexity-</b></a> It is a measurement of rate of growth of time taken by any algorithm with respect to the increase in input size.</span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><a name="spacecomplexity"><b>Space Complexity-</b></a> Similar to the time complexity, it is a measurement of rate of growth of memory space taken by any algorithm with respect to the increase in input size.</span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><a name="asymptotic"><b>Asymptotic Notation-</b></a> It is a standard used for determining time/space complexities of an algorithm.</span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;">There are three basic asymptotic notations-</span></div>
<div class="MsoNormal">
</div>
<ol style="text-align: left;">
<li><span style="font-family: "verdana" , sans-serif;"><a href="#bigo">Big O Notation [O]</a></span></li>
<li><span style="font-family: "verdana" , sans-serif;"><a href="http://javagreedy.blogspot.in/2016/06/asymptotic-notations-big-omega-notation.html#bigomega" target="_blank">Big Omega Notation [Ω]</a></span></li>
<li><span style="font-family: "verdana" , sans-serif;"><a href="http://javagreedy.blogspot.in/2016/06/asymptotic-notations-big-omega-notation.html#bigtheta" target="_blank">Big Theta Notation [θ]</a></span></li>
</ol>
<b style="font-family: Verdana, sans-serif;"><a name="bigo">1. Big O Notation [O]</a></b><br />
<br />
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;">This notation represents tight upper bound of the given function.</span><br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkXSorh92MREacNDDPpvdPdsgx3MdDePNociN8wSznxRDmk0a_QgW_9jC8A376jMPy2nV557oCgVSpzXQrVAbcncGPqPU5nEv5jYZhn0awXUBltl4IAJAJJIfLavdldiKloneOXQoIfCw/s1600/BigO.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img alt="Big O" border="0" height="285" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkXSorh92MREacNDDPpvdPdsgx3MdDePNociN8wSznxRDmk0a_QgW_9jC8A376jMPy2nV557oCgVSpzXQrVAbcncGPqPU5nEv5jYZhn0awXUBltl4IAJAJJIfLavdldiKloneOXQoIfCw/s320/BigO.jpg" title="Big O" width="320" /></a></div>
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">Analytically we say as:<span class="apple-converted-space"> </span></span><i style="font-family: Verdana, sans-serif;"><span lang="EN-US" style="background: white;">f</span></i><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">(<i>n</i>)</span><span class="apple-converted-space" style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;"> belongs to</span></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"> O(</span><i style="font-family: Verdana, sans-serif;"><span lang="EN-US" style="background: white;">g</span></i><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">(<i>n</i>)</span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">) as there exists<span class="apple-converted-space"> </span><i>c</i> > 0
(e.g.,<span class="apple-converted-space"> </span><i>c</i> = 1)
and<span class="apple-converted-space"> <i>n</i></span>0 (e.g.<span class="apple-converted-space"> <i>n</i></span>0 = 5) such that<span class="apple-converted-space"> </span></span><i style="font-family: Verdana, sans-serif;"><span lang="EN-US" style="background: white;">f</span></i><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">(<i>n</i>)</span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"> ≤ <i>c</i></span><i style="font-family: Verdana, sans-serif;"><span lang="EN-US" style="background: white;">g</span></i><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">(<i>n</i>)</span><span class="apple-converted-space" style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;"> </span></span><span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;">whenever<span class="apple-converted-space"> <i>n</i></span> ≥ <i>n</i>0.</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">Lets see it through an example-<o:p></o:p></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">We have another function f(n) = 5n+4. Lets find the
tightest upper bound of this function. By tightest upper bound I mean we have
to find an another function (say g(n))
that will be always higher when we multiply g(n) by some constant (say
c) and add some value of n (say n0) to it.<o:p></o:p></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;">By looking to f(n) we can say that if we have a
function g(n) = 6n then it will be the tightest upper bound of f(n). </span><span lang="EN-US" style="background: white;">In other words: </span><i><span lang="EN-US" style="background: white;">f</span></i><span lang="EN-US" style="background: white;">(n)</span><span lang="EN-US" style="background: white;"> ≤ <i>c</i></span><i><span lang="EN-US" style="background: white;">g</span></i><span lang="EN-US" style="background: white;">(n)</span><span class="apple-converted-space"><span lang="EN-US" style="background: white;"> </span></span><span lang="EN-US" style="background: white;">for c=6
& n0=4. To represent it in Big O we say f(n) = O(n) & it is read as </span><i><b>"f of n is big oh of g of n"</b></i>.</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">Now you might say what if you have taken g(n) =
6n<sup>2</sup> or g(n) = 6n<sup>3 </sup>?<o:p></o:p></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;">Well, you are right! And in this case complexity will be O(n<sup>2</sup>)
and O(n<sup>3</sup>) respectively because f(n) will always be less than or
equal to g(n) for any value of n. <o:p></o:p></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;">But since we use Big O notation to represent <u>tightest
upper bound</u> of the function, we will say f(n) = O(n) instead of O(n<sup>2</sup>)
or O(n<sup>3</sup>).</span><span style="font-family: "arial" , sans-serif;"><o:p></o:p></span></span><br />
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span>
<span lang="EN-US" style="background: white; font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;">Big O notation is usually used to specify time/space complexity of the given algorithm in <b>worst case </b>scenario. </span></span><span style="background-color: white; font-family: "verdana" , sans-serif;"><a name="worstcase">Worst case scenario is the situation when algorithm takes maximum time to run or maximum memory during it's execution.</a></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: "verdana" , sans-serif;"><span lang="EN-US" style="background: white;"><o:p>In the next post we will see </o:p></span><span style="font-family: "verdana" , sans-serif;"><a href="http://javagreedy.blogspot.in/2016/06/asymptotic-notations-big-omega-notation.html">Big Omega & Theta Notations</a>.</span></span><br />
<span style="font-family: "verdana" , sans-serif;"><span style="font-family: "verdana" , sans-serif;"><br /></span></span></div>
</div>Rahul Askarhttp://www.blogger.com/profile/10523230965873417240noreply@blogger.com0