Questions tagged [big-o-notation]

Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation.

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
36 views

Summing big-O-notation

prove or disprove $$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$ I have no idea about where to begin. what are the theories which should be used here?
0
votes
0answers
28 views

How to find running time complexity of divide and conquer method without Master Theorem

I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
0
votes
0answers
24 views

Asymptotics and logarithms/exponents

We have four categories: additive constants, multiplicative constants, polynomials, and exponentials When determining the growth order of functions, we only care about polynomials and ...
0
votes
1answer
135 views

heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
0
votes
0answers
30 views

Splay tree amortized cost analysis

I am looking into the amortized analysis of splay trees and seem to be missing something. Pretty much every resource uses the accounting method which I believe I grasp. What confuses me is the part ...
0
votes
0answers
37 views

Probability in 1-universal hash function

I am trying to prepare for an exam and I am not sure how to solve this task: Given is a hash function with m buckets, which uses a 1-universal hash function h: U -> H and handles collisions with ...