Scribd
Upload
16 views7 pages

Understanding Big O Notation in Java

This document discusses big O notation and time complexity analysis in algorithms. It defines big O notation as providing an asymptotic upper bound on the growth rate of a function. A function's time complexity is described using big O notation, ignoring constant factors and lower order terms to focus on the dominant term. Tighter bounds should be used when possible to more accurately characterize a function's growth rate.

Uploaded by

onlineearningfor
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views7 pages

Understanding Big O Notation in Java

This document discusses big O notation and time complexity analysis in algorithms. It defines big O notation as providing an asymptotic upper bound on the growth rate of a function. A function's time complexity is described using big O notation, ignoring constant factors and lower order terms to focus on the dominant term. Tighter bounds should be used when possible to more accurately characterize a function's growth rate.

Uploaded by

onlineearningfor
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Part 2

Java

Hira Awais
Lecturer (DCS)
DDSA (FOC)
 Slide courtesy : Dr. Zahid Halim
 The 5N+3 time bound is said to "grow asymptotically" like N
 This gives us an approximation of the complexity of the
algorithm
 Ignores lots of (machine dependent) details, concentrate on
the bigger picture
 Big Oh Notation: Upper bound
 Omega Notation: Lower bound
 Theta Notation: Tighter bound
 To denote asymptotic upper bound, we use O-notation.
 For a given function g(n), we denote by O(g(n)) (pronounced
“big-oh of g of n”) the set of functions:
 O(g(n))= { f(n) : there exist positive constants c and n0 such
that 0≤f(n)≤c∗g(n) for all n≥n0 }
Which function is better? 4000

10 n2 Vs n3 3500

3000

2500

10 n^2
2000
n^3

1500

1000

500

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
 Even though it is correct to say “7n - 3 is O(n3)”, a better
statement is “7n - 3 is O(n)”, that is, one should make the
approximation as tight as possible
 Simple Rule:
Drop lower order terms and constant factors
7n-3 is O(n)
8n2log n + 5n2 + n is O(n2log n)

You might also like