Showing posts with label Data Structures and Algorithms. Show all posts
Showing posts with label Data Structures and Algorithms. Show all posts

Go Tutorial Part 4 (Interfaces, Routines, Channels, Concurrency in Go)

GO - Part 4

Credit goes to - Master the fundamentals and advanced features of the Go Programming Language (Golang), on Udemy by Stephen Grider.
I have tried some snippets on my own and some are referring to the snippets developed while going through the course.

Code Repo: https://github.com/namitsharma99/goLangTutorials




Interfaces
- - - - - - - - - 

Need:
Whenever there is a logic change in a function, it has to be re-written.


For example, maintaining 2 chatboxes :
A.
1. type hindiBot struct

2. func (hindiBot) getGreeting() string // return "namaste"

3. func printGreeting(hb hindiBot) // similar code - fmt.Println(hb.getGreeting())

B.
1. type englishBot struct

2. func (englishBot) getGreeting() string // return "hello"

3. func printGreeting(eb englishBot) // similar code - fmt.Println(eb.getGreeting())


Code --

package main

import "fmt"

type hindiBot struct {}
type englishBot struct {}

func main()  {

}

//func (hb hindiBot) getGreeting() string {
func (hindiBot) getGreeting() string {  // since no hb value is read
  return "namaste!!"
}

// func (eb englishBot) getGreeting() string {
func (eb englishBot) getGreeting() string { // since no eb value is read
  return "hello!!"
}

func printGreeting(hb hindiBot) {
  fmt.Println(hb.getGreeting())
}

func printGreeting(eb englishBot) {
  fmt.Println(eb.getGreeting())
}

ERROR::

$ go build main.go 
# command-line-arguments
./main.go:26:6: printGreeting redeclared in this block
previous declaration at ./main.go:22:23


FIX 1:

package main

import "fmt"

type hindiBot struct {}
type englishBot struct {}

func main()  {
  hb := hindiBot{}
  eb := englishBot{} // gives error

  printGreeting(hb)
  printGreeting(eb)

}

//func (hb hindiBot) getGreeting() string {
func (hindiBot) getGreeting() string {  // since no hb value is read
  return "namaste!!"
}

// func (eb englishBot) getGreeting() string {
func (eb englishBot) getGreeting() string { // since no eb value is read
  return "hello!!"
}

// ERROR
/* func printGreeting(hb hindiBot) {
  fmt.Println(hb.getGreeting())
}

func printGreeting(eb englishBot) {
  fmt.Println(eb.getGreeting())
} */
// printGreeting redeclared in this block

// using single print method
func printGreeting(hb hindiBot) {
  fmt.Println(hb.getGreeting())
}

ERROR::
$ go build main.go 
# command-line-arguments
./main.go:13:16: cannot use eb (type englishBot) as type hindiBot in argument to printGreeting


FIX 2: 

-- using interfaces

package main

import "fmt"

// the interface fix
type bot interface {
  getGreeting() string
}


type hindiBot struct {}
type englishBot struct {}

func main()  {
  hb := hindiBot{}
  eb := englishBot{}

  printGreeting(hb)
  printGreeting(eb)

}

//func (hb hindiBot) getGreeting() string {
func (hindiBot) getGreeting() string {  // since no hb value is read
  return "namaste!!"
}

// func (eb englishBot) getGreeting() string {
func (eb englishBot) getGreeting() string { // since no eb value is read
  return "hello!!"
}

// ERROR
/* func printGreeting(hb hindiBot) {
  fmt.Println(hb.getGreeting())
}

func printGreeting(eb englishBot) {
  fmt.Println(eb.getGreeting())
} */
// printGreeting redeclared in this block

func printGreeting(b bot) {
  fmt.Println(b.getGreeting())
}


O/P
- - -

$ ./main 
namaste!!
hello!!


WORKING:

Interface identifies based on the func associated.

type bot interface {
  getGreeting() string
}

This declares that any type, having getGreeting() func and returning the string, automatically becomes a member of this interface

Since hb and eb above, are now the members, they can call the printGreeting() func easily using the bot interface

Note:
------
Argument type can also be put in the clause along with the type check as follows :

type bot interface {
  getGreeting(string, int) string
  // and many other functions
}


- interfaces are not generic types
- interfaces are implicit, matched with signature clauses only
- interfaces just help in maintaining types, no further validation



net/ http 
- - - - - - - - 

package main

import "fmt"
import "net/http"
import "os"

func main() {
  resp, err := http.Get("http://www.google.com")
  if nil != err {
    fmt.Println("Error: ", err)
    os.Exit(1)
  }
  fmt.Println("response: ",resp)
}

O/P
- - -

$ ./main 
response:  &{200 OK 200 HTTP/1.1 1 1 map[Cache-Control:[private, max-age=0] Content-Type:[text/html; charset=ISO-8859-1] Date:[Wed, 20 May 2020 21:41:29 GMT] Expires:[-1] P3p:[CP="This is not a P3P policy! See g.co/p3phelp for more info."] Server:[gws] Set-Cookie:[1P_JAR=2020-05-20-21; expires=Fri, 19-Jun-2020 21:41:29 GMT; path=/; domain=.google.com; Secure NID=204=V-0Lr33CGR1OSs2-eLQShrsFqM23NpD66sBXPp4lJky4VKQ1LSL6Uoz6SpRpUuDB8HToPfN6YFbT_cgGjnO595t07MExURpcb5UeC_juxvM0dMZrQduvG8FUJ5gsIzCNGCWumrxNWyrEhntEvhUBw9rfjkE9w6u7zzoq3_05ltI; expires=Thu, 19-Nov-2020 21:41:29 GMT; path=/; domain=.google.com; HttpOnly] X-Frame-Options:[SAMEORIGIN] X-Xss-Protection:[0]] 0xc00011e0e0 -1 [] false true map[] 0xc0001ee000 <nil>}



Some more info on Interfaces
- - - - - - - - - - - - - - - - - - - - - - - - -

Reader Interface - provides common implementation to read any source as byte slice - []byte, which can work with anything further

package main

import "fmt"
import "net/http"
import "os"

func main() {
  resp, err := http.Get("http://www.google.com")
  if nil != err {
    fmt.Println("Error: ", err)
    os.Exit(1)
  }
  // fmt.Println("response: ",resp)
  bs := make([]byte, 99999)
  resp.Body.Read(bs)
  fmt.Println("byte slice: ", bs)
  fmt.Println("byte slice as string: ", string(bs))

}


O/P
---
< Many byte characters and huge response >

Another option to print response -
...
io.Copy(os.Stdout, resp.Body)
...


Writer Interface - opposite of Reader interface, takes byte slice and converts into desired format

io.Copy(os.Stdout, resp.Body) --> the params are implementation of Writer interface and Reader interface respectively

Copy() internally uses CopyBuffer()


package main

import "fmt"
import "net/http"
import "os"
import "io"

type logWriter struct {}

func main() {
  resp, err := http.Get("http://www.google.com")
  if nil != err {
    fmt.Println("Error: ", err)
    os.Exit(1)
  }
  // fmt.Println("response: ",resp)

  // bs := make([]byte, 99999)
  // resp.Body.Read(bs)
  // fmt.Println("byte slice: ", bs)
  // fmt.Println("byte slice as string: ", string(bs))

  // io.Copy(os.Stdout, resp.Body)

  lw := logWriter{}
  io.Copy(lw, resp.Body)

}

func (logWriter) Write(bs []byte) (int, error) {
  // return 1, nil
  fmt.Println(string(bs))
  fmt.Println("length ---- ", len(bs))
  return len(bs), nil
}

o/p
- - - 

< response body >



Channels and Go Routines
- - - - - - - - - - - - - - - - - - - - - - -

Example Code:

main.go
- - - - 
package main

import "fmt"
import "net/http"

func main() {
  links := []string {
    "http://www.google.com",
    "http://www.golang.org",
    "http://www.stackoverflow.com",
    "http://www.amazon.com",
  }

  for _, link := range links {
    checkLink(link)
  }

}

func checkLink(link string) {
  _, err := http.Get(link)
  if nil != err {
    fmt.Println(link, " is down!!")
    return
  }
  fmt.Println(link, " is up!!")
}

O/P
- - -

$ ./main 
http://www.google.com  is up!!
http://www.golang.org  is up!!
http://www.stackoverflow.com  is up!!
http://www.amazon.com  is up!!



Note: As clear from the response, this is sequential and involves waiting. Now, need to see how to make the calls in parallel - Go Routines.

Go Routine lets the Main Routines knows, that there is a blocking function and Main should continue.

Syntax: just need to add go prefix against the function calls
go checkLink(link)

Go Scheduler takes care of the monitoring. Be default, it uses only one CPU core, but it can be customized to distribute the load.

Concurrency/ Parallelism can be achieved once multiple cores are involved.

Main routine doesn't give any priority to the child routines hence they are not executed. Therefore, need to use Channels.
It acts as a mediator to communicate between the Main routine and the child routines.
Channels are strictly defined per types, string channel can't support the int type.


How to send data with Channels

channel <- 9         : send the value 9 into channel
n <- channel         : waiting for channel to get the value and assigning it further to the variable n

fmt.Println(<- channel) : waiting for channel to get the value and hence printing it afterwards


Code:

main.go
- - - - - -
package main

import "fmt"
import "net/http"

func main() {
  links := []string {
    "http://www.google.com",
    "http://www.golang.org",
    "http://www.stackoverflow.com",
    "http://www.amazon.com",
  }

  c := make(chan string) // need to pass this channel in function call

  for _, link := range links {
    go checkLink(link, c)
  }
  fmt.Println(<- c)
}

func checkLink(link string, c chan string) {
  _, err := http.Get(link)
  if nil != err {
    fmt.Println(link, " is down!!")
    c <- "down !!"
    return
  }
  fmt.Println(link, " is up!!")
  c <- "up!!"
}


O/P
- - -
$ ./main 
http://www.google.com  is up!!
up!!


One issue - only one url is checked...

Because, Main Routine proceeds as soon as one of the child routines comes back.
Message receiving is also a blocking code.

Making the channel receiver again in Main routine -

...
  fmt.Println(<- c)
  fmt.Println(<- c)
...
O/P
- - -
$ ./main 
http://www.google.com  is up!!
up!!
http://www.stackoverflow.com  is up!!
up!!

All results can be seen if same number of receivers are created, but hangs if any additional is there !!

Quick hack -
...
  for i :=0; i< len(links); i++ {
    fmt.Println(<- c)
  }
...



How to repeat the Routines?
- - - - - - - - - - - - - - - - - - - - - - - 

Passing links instead of values, and handling at the receiver ends

package main

import "fmt"
import "net/http"

func main() {
  links := []string {
    "http://www.google.com",
    "http://www.golang.org",
    "http://www.stackoverflow.com",
    "http://www.amazon.com",
  }

  c := make(chan string) // need to pass this channel in function call

  for _, link := range links {
    go checkLink(link, c)
  }
  // fmt.Println(<- c)
  // fmt.Println(<- c)

  // for i :=0; i< len(links); i++ {
  //   fmt.Println(<- c)
  // }

  for {
    go checkLink(<- c, c)
  }

}

func checkLink(link string, c chan string) {
  _, err := http.Get(link)
  if nil != err {
    fmt.Println(link, " is down!!")
    // c <- "down !!"
    c <- link
    return
  }
  fmt.Println(link, " is up!!")
  // c <- "up!!"
  c <- link
}


O/P
- - - 
< Going on and on... forever>



Alternatively, making it more readable --
...
  for l := range c {
    go checkLink(l, c)
  }
...



How to add a pause in between the checks?
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

Use Time package, sleep function
Avoid adding pauses in the main routines, it's a bad way - blocking and queuing 

Use function literals, i.e. unnamed functions

func main() {
  links := []string {
    "http://www.google.com",
    "http://www.golang.org",
    "http://www.stackoverflow.com",
    "http://www.amazon.com",
  }

  c := make(chan string) // need to pass this channel in function call

  for _, link := range links {
    go checkLink(link, c)
  }

  // Alternative syntax
  for l := range c {
    // time.Sleep(5*time.Second) // 5 seconds, bad way - blocking and queuing
    // go checkLink(l, c)
    go func() {  // function literals, like unnamed and anonymous functions
        time.Sleep(5*time.Second)
        go checkLink(l, c)
      }  ()
  }

}

Issue: l is not a trustworthy variable to monitor for the Main routine, as it's value might have changed.
Output can be like first run happening fine for all URLs but after that stuck with one url's copy. (Go being pass by copy)

Fix, pass l from the range -
...
  for l := range c {
    go func(link string) {  
        time.Sleep(5*time.Second)
        go checkLink(link, c)
      }  (l)
  }
...

O/P AS EXPECTED -
- - - - - - - - - 

$ ./main 
http://www.google.com  is up!!
http://www.stackoverflow.com  is up!!
http://www.amazon.com  is up!!
http://www.golang.org  is up!!
http://www.google.com  is up!!
http://www.stackoverflow.com  is up!!
http://www.amazon.com  is up!!
http://www.golang.org  is up!!
http://www.google.com  is up!!
http://www.stackoverflow.com  is up!!
http://www.amazon.com  is up!!
^C

Go Tutorial Part 3 (Structs, Pointers and References, Maps, Structs vs Maps in Go)

GO - Part 3

Credit goes to - Master the fundamentals and advanced features of the Go Programming Language (Golang), on Udemy by Stephen Grider.
I have tried some snippets on my own and some are referring to the snippets developed while going through the course.

Code Repo: https://github.com/namitsharma99/goLangTutorials



Structs data structure
- - - - - - - - - - - - - - - - - - 
- collection of properties related together

2 steps to define structs:
1. provide GO, the fields struct should have
2. create the object using the above


main.go
- - - - 

package main

import "fmt"

type person struct {
  firstName string
  lastName string
}

func main() {
  buddy := person {"code", "buddy"} // not a good practice as it depends on positions
  namit := person {firstName: "Namit", lastName: "Sharma"}

  fmt.Println(buddy)
  fmt.Println(namit)
}

O/P
- - - 

$ go build
$ ls
  main.go structs
$ ./structs 
  {code buddy}
  {Namit Sharma}

For uninitialized structs, if we want to see the struct signature - 

...
  var human person
  fmt.Println(human)
  fmt.Printf("%+v", human)
...

o/p
- - -
{ }
{firstName: lastName:}


...
  human.firstName = "ABC"
  human.lastName = "DEF"

  fmt.Println(human)
  fmt.Printf("%+v", human)
...

o/p
- - -
{ABC DEF}
{firstName:ABC lastName:DEF}




Nested Structs
- - - - - - - - - - - - -

package main

import "fmt"

type contactInfo struct {
  email string
  zipCode int
}

type person struct {
  firstName string
  lastName string
  contact contactInfo
}

func main() {
 
  newPerson := person {
    firstName:"Namit",
    lastName:"Sharma",
    contact: contactInfo {
      email: "thecodebuddy.blogspot.in",
      zipCode: 60001,
    },
  }
  // multiline declarations should have commas at the end
  
  fmt.Println("%+v", newPerson)

}

o/p
- - -

$ ./main 
%+v {Namit Sharma {thecodebuddy.blogspot.in 60001}}


Note - if the name of the variable is same as the type name, just use type - 

package main
import "fmt"

type contactInfo struct {
  email string
  zipCode int
}

type person struct {
  firstName string
  lastName string
  contactInfo
}

func main() {

newPerson := person {
    firstName:"Namit",
    lastName:"Sharma",
    contactInfo: contactInfo {
      email: "thecodebuddy.blogspot.in",
      zipCode: 60001,
    },
  }
  // multiline declarations should have commas at the end

  fmt.Printf("%+v", newPerson)
  fmt.Println("")

}

o/p
- - -

$ ./main 
{firstName:Namit lastName:Sharma contactInfo:{email:thecodebuddy.blogspot.in zipCode:60001}}



 
Structs and Receiver Functions
- - - - - - - - - - - - - - - - - - - - - - - - - - 

func main () {
...
  fmt.Printf("%+v", newPerson)
  fmt.Println("")
  newPerson.print()
...
}

o/p
- - - 

{firstName:Namit lastName:Sharma contactInfo:{email:thecodebuddy.blogspot.in zipCode:60001}}
{firstName:Namit lastName:Sharma contactInfo:{email:thecodebuddy.blogspot.in zipCode:60001}}




Updating values inside struct
- - - - - - - - - - - - - - - - - - - - - - - - -

func (p person) updateName(newFirstName string) {
  p.firstName = newFirstName
}


This fails as there is another memory allocated to the changes made, original reference has no impact (pass by copy), therefore use pointers

...
  fmt.Println("updating name::")
  newPersonPointer := &newPerson  // Optional to define a pointer to person, func can accept the person object as well
  newPersonPointer.updateName("XYZ")
  newPersonPointer.print()
...

func (ptr *person) updateName(newFirstName string) {
  (*ptr).firstName = newFirstName
}


o/p
- - -
updating name::
{firstName:XYZ lastName:Sharma contactInfo:{email:thecodebuddy.blogspot.in zipCode:60001}}


Explanation -

& operator : memory address of variable
* operator : value at the address

Rules:
1. To turn address into value, use *address
2. To turn value into address, use &value



Note::

Pointers are not required while working with Slices
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Slices internally use Arrays

Slice = length | capacity | ptr to head of array

Now while making any change to slices, a copy of slice is created, but still it is pointing to the actual address
Hence it works without any fail.
Therefore, a slice is called as of 'Reference Type'.

Value Types: int, float, string, bool, structs  (use pointers while working with these)
Reference Types: slices, maps, channels, pointers, functions




Maps
- - - - -

All keys of same type
All values of same type


main.go
-------
package main

import "fmt"

func main() {
  colors := map[string] string {
    "red" : "#ff0000",
    "green" : "#433243",
  }
  fmt.Println(colors)
}

O/P
- - -
$ ./main 
map[green:#433243 red:#ff0000]


Also, map be declared as - 
1. var colors map[string] string
2. colors := make(map[string]string)

func main() {
  // colors := map[string] string {
  //   "red" : "#ff0000",
  //   "green" : "#433243",
  // }

  // var colors map[string] string
  colors := make(map[string]string)

  colors["white"] = "#ffffff"
  colors["grey"] = "#222222"
  fmt.Println(colors)

  delete(colors, "white")  // to delete using a key
  fmt.Println(colors)
}

O/P
- - -
$ ./main 
map[grey:#222222 white:#ffffff]
map[grey:#222222]



Map Iteration
- - - - - - - - - - - -

func printMap (c map[string]string ) {
  for color, hex := range c {
    fmt.Println("Hex code for ", color, "is ", hex)
  }
}

main.go
...
printMap(colors)
...

o/p
- - -
$ ./main 
map[grey:#222222 white:#ffffff]
Hex code for  white is  #ffffff
Hex code for  grey is  #222222



Map vs Structs
- - - - - - - - - - - - 

Map - 
  • same typed keys
  • same typed values
  • keys are indexed and iterable
  • used to represent collection of related properties
  • no need to have all keys available at compile time
  • reference type

Struct -
  • diff types of values
  • keys are not indexed
  • can be used to represent collection of different properties
  • no need to know all the different fields at compile time
  • value type



How to count the number of leaves in a binary tree?


Hello Buddies.


Here's a quick code snippet for finding the number of leaves in a 'Binary Tree', after a node gets deleted!





Have a look-

Input -

5
-1 0 0 1 1
1


Input description -

Line 1: No. of nodes in Binary Tree
Line 2: All the nodes' parents, where -1 means no parent - root, 0 means root as parent.
Line 3: Node at which this value exists, remove it.


Node to remove -



public class TreeProblem {
 private static int count = 0;

 public static void main(String args[]) throws Exception {

  Scanner scanner = new Scanner(System.in);
  int numOfNodes = scanner.nextInt();
  scanner.nextLine();
  String intStr = scanner.nextLine();
  String[] array = intStr.split(" ");
  int[] arr = new int[array.length];
  for (int i = 0; i < numOfNodes; i++) {
   arr[i] = Integer.valueOf(array[i]);
  }
  int nodeToDelete = scanner.nextInt();

  // create a tree
  Node root = null;
  int valueIndex = 0;
  Node current = null;
  for (int i = 0; i < numOfNodes; i++) {
   if (arr[i] == -1) {
    root = new Node(valueIndex++);
    current = root;
   } else {
    if (arr[i] == current.value) {
     if (null == current.left) {
      current.left = new Node(valueIndex++);
     } else if (null == current.right) {
      current.right = new Node(valueIndex++);
      current = current.left;
     }
    }
   }
  }

  // scan the tree for deleting the node
  // it clearly means we have to ignore the leaves at that node, for the remaining
  // keep the count going

  treetraversal(root, nodeToDelete);

  System.out.println("Remaining leaves = " + count);
  scanner.close();
 }

 private static void treetraversal(Node root, int nodeToDelete) {
  if (null == root) {
   return;
  }
  System.out.println("-- " + root.value);
  if (root.value == nodeToDelete) {
   return;
  }
  if (null != root.left) {
   treetraversal(root.left, nodeToDelete);
  }
  if (null != root.right) {
   treetraversal(root.right, nodeToDelete);
  }
  if (null == root.left && null == root.right) {
   count++;
  }
 }

}

class Node {

 int value;
 Node parent, left, right;

 Node(int value) {
  this.value = value;
 }
}

Data Structures and Algorithms | Complexity Analysis | Linear and Binary Search







When we write a code, many a times it happens that the functionality is met, but still the way the code runs with, doesn’t please the perfectionist developer inside us.

Those buddies who are well experienced with difficult stakeholders, clients or even interviewers, may know the pain, when someone says “Your code works fine, but still it doesn’t look efficient… “.

To avoid such encounters, it becomes crucial to emphasize on the complexity analysis of the algorithm, at the very early stages of the career. But as we always say, it's never too late to start a good practice.

So this time, we will use this post to go through OR revisit the concepts of ‘Complexity Analysis’.

And it is promised, that the following posts will try to dig a deeper insight in the ‘Data Structures And Algorithm’ arena.




How complexity is analysed?

There are N number of ways to do so, but the heroes that beat us often while writing the code are -
  1. Space Complexity
  2. Time Complexity

Disclaimer: The more you go inside these topics the more you will deviate towards the Maths you saw during Engineering :P

But we will stick to the useful take-aways that will help us in day-to-day coding and facing challenging problems.




Complexity here considers the memory the code is consuming and the time it is taking to process.




Space Complexity

With respect to JAVA, we can figure out how the memory management will be taking place while writing. What to consider here is -
1. Fixed consumption
The variables and constants defined during coding, being consumed for sure in the code path.
2. Variable consumption
The variables used for conditional assignments and calculations.




I would like to reflect the above with a small example here -

Consider the following snippet -

int a = 2;   // fixed 4 bytes
int b = 3; // fixed 4 bytes

if (a>b) {
return a;      // conditional 0 byte
} else {
int c = a*2 + c*3;
   // conditional
// allocates additional memory to store c
// and do the calculations
return c;
}


Cool Tip:
For more info, we can spend some time going through computer science books and learn how internal memory allocation works.





Time Complexity

This champ will be under the limelight if you are aiming at cracking IT giants, or want to mark your presence in various coding competitions.

It undertakes the compile and the process time, hence making us sure that the code works within the expected time limits.

So here the fixed factor is the ‘Compile Time’, and the variable one is ‘Process Time’.

I would like to share the 3 ways we can follow, which I read in a very good article long back, consolidated briefly, but unfortunately forgot the source.




1. Note the time, before the operation starts and after it ends. Get the difference and you get an idea of the time taken.

2. Do a dry run. I.e. grab a pen and paper, and execute the code step by step. This way you will consider all the loops and and iterations and get an idea on how effective your code is, is there any way to make it run better, are there any vague iterations, and so on.
A very helpful outcome of the point#2 strategy is that it makes you answerable well if you are asked by someone for N number of iterations.

For example,
When you are iterating N X N matrix, clearly you are involving 2 for loops.
Outer loop iteration 1 -> inner full iterations - N
Outer loop iteration 2 -> inner full iterations - N
Outer loop iteration 3 -> inner full iterations - N
.
. and so on...
.
Outer loop iteration N -> inner full iterations - N

Hence it takes N^2 steps.

But imagine if the number of iterations increase to millions or billions, you will be clever enough to not to start dry running with this much number. This is where point#3 comes to rescue.

3. Asymptotic Analysis.

Where your maths and calculus skills will be at stake. (Kidding, just do a smart work here and learn what exactly it tries to say!)
This analysis aims at giving an estimate about the code’s behavior, when number of iterations exceed manual control, and it comes in 3 flavors -

A. Big O Notation
Worst Case - when you get the result in the last step.
Upper Bound -
denoted as

                    f(n)=O(g(n))f(n)=O(g(n))

if and only if there exists constants k and n such that,

                    |f(x)|≤k|g(x)|∀x>n

B. Big Theta Notation
Average Case - what it generally takes on an average to get the result.
denoted as
                   
                    f(n)=θ(g(n))f(n)=θ(g(n))

if and only if there exists constants j,k and n such that,                   

                    j|g(x)|≤|f(x)|≤k|g(x)|∀x>n

C. Big Omega Notation
Best Case - when you get the result in first step.
denoted as

                    f(n)=Ω(g(n))f(n)=Ω(g(n))

if and only if there exists constants k and n such that,

                    |f(x)|≥k|g(x)|∀x>n
Thanks to this answer on Quora for sharing formulas, and making my life easier. LOL.




If you have time, check this out for how these actually are understood with the help of graphs.

So you can take away the following for now, if you are not having enough time to explore -

1. Use Big O in interviews and technical discussions, because no one will give you the best case scenario. Always prepare for the worst case scenario and hope for the best ;)
2. Big Theta is helpful to generalize an algo, using the average cases. Hence do some head banging on it whenever time allows you.
3. Big Omega is a dreamy concept, hence you can leave it for the last.




Moving on, as we have a custom here on TCB, we believe in demo and practicals more than the theory, so here we go.


Kicking off with the first step in Data Structures - Searching an element.


So broadly speaking we have 2 types of searches -

Unordered and Ordered.


Unordered -
That means no order is being followed in the elements’ placement, and for the very worst, you can assume that the element to be searched is at the end, and you are scanning from the beginning.
So If there are N elements, it requires N iterations and the operation would be of order O(N).


Ordered -
That means there is a logical order while placing the elements, either natural or alphabetical. 2 generally used ordered searches - Linear and Binary.

For Linear search, efficiency depends on the average number of steps taken i.e. if there are N elements, operation would be of O(N/2).

For Binary search also, the efficiency depends on the average number of steps taken, but since we are always having half of the steps remaining with each and every iteration, it introduces the overall function’s behavior as that of mathematical log function.
Hence it reflects as O(log2(N)).


To see how the search algorithms work feel free to drop by at some previously created blogs, just for you -







Now, let’s take a deep dive on the analysis of time taken.

Say time taken is directly dependent on the order of processing, hence in terms of equation it can be shown as:
T = K * log2(N).

To make it more clear on how steps can be realized, have a look at this example:

For 10 elements →  
The number of steps taken would be log2(10) ~= 3.322 ~= 4
Shortcut Tip:
Simply find the nearest power of 2 i.e. 2^3 = 8, but it’s lesser than 10, and we want to cover entire 10 elements. Hence 2^4 = 16 > 10, so 4 steps to cover 10 elements.

Similarly, for 100 elements → number of steps = log2(100) = 2*3.322 = 6.644 ~= 7 steps
Shortcut Tip:
Simply 2^6 = 64 < 100, hence 2^7 = 128 > 100, hence 7 steps to cover 100 elements... and so on...

Practice Tip:
Do some mathematical analysis on finding the number of steps taken. Once done with this, it won’t look much difficult.

Before leaving let’s have a quick look at some take aways -

Big O Notation - a rough measure of complexity
T:   time taken
N:  number of elements


1. Insert an element into an unordered array -

T = K (constant), since it is not dependent N. Complexity ~ O(1)

2. Performing a Linear Search

T = K * N/2. Complexity ~ O(N)

3. Performing Binary Search

T = K * log2(N). Complexity ~ O(log2(N))

4. For ordered array insert, delete, and unordered delete

Complexity ~ O(n)

And the rest is up to you. :)

You can dig as much as you want and do share your thoughts and feedback.
Those are always welcome and looked upon for making this place a better one for the coders.




Next series of blogs will be covering few more Data Structures’ concepts.




Cheers!!

Happy Coding.






















Featured post

Oracle SQL Scheduled Jobs - An Interesting Approach

  Oracle SQL Scheduled Jobs A DB Scheduler is the best way to automate any backend database job. For instance, if you want to process the p...