Classifying T(n) as O(f(n)): O(n)

  • Thread starter ZERO_COOL
  • Start date
In summary: T(n) = 5 + 5n is O(n) as 5n is the highest order term and thus the function grows at the same rate as n. Therefore T(n) is classified as O(n).In summary, T(n) can be classified as O(n) based on the function T(n) = 5 + 5n and the given recurrence system T(n) = 5 + T(n - 1) (n > 0) with T(0) = 4.
  • #1
ZERO_COOL
17
0

Homework Statement


Give a classification of T(n) as O(f(n)) for a suitable function f in the hierarchy of Big Oh.

Homework Equations


T(n) = 5 + T(n - 1) (n > 0) *THIS IS PART OF THE RECURRENCE SYSTEM.

T(n) = 5 + 5N. *THIS IS THE FORMULA FOR THE TIME COMPLEXITY FUNCTION. WORKED OUT BY SOLVING THE RECURRENCE SYSTEM.

The Attempt at a Solution


I've got confused, not sure if I give a classification of the formula that I worked out by solving the recurrence system or of the recurrence system.

I think it is the formula T(n) = 5 + 5n. In which case I *think* it's a no brainer because the only term is 5n and so,

T(n) = 5n is (O^2) and also it is O(n). Thus T(n) = 5n is of order n. Which means 5n is BIG THETA O(n).

Would appreciate ir if someone could verify I'm on the right track with this.
 
Physics news on Phys.org
  • #2
ZERO_COOL said:

Homework Statement


Give a classification of T(n) as O(f(n)) for a suitable function f in the hierarchy of Big Oh.

Homework Equations


T(n) = 5 + T(n - 1) (n > 0) *THIS IS PART OF THE RECURRENCE SYSTEM.
You're missing something - what is T(1)? Without this I can't verify your non-recursive formula.
ZERO_COOL said:
T(n) = 5 + 5N. *THIS IS THE FORMULA FOR THE TIME COMPLEXITY FUNCTION. WORKED OUT BY SOLVING THE RECURRENCE SYSTEM.

The Attempt at a Solution


I've got confused, not sure if I give a classification of the formula that I worked out by solving the recurrence system or of the recurrence system.

I think it is the formula T(n) = 5 + 5n. In which case I *think* it's a no brainer because the only term is 5n and so,

T(n) = 5n is (O^2) and also it is O(n). Thus T(n) = 5n is of order n. Which means 5n is BIG THETA O(n).

Would appreciate ir if someone could verify I'm on the right track with this.

If T(n) = 5 + 5n, then T(n) is O(n). I have no idea what O^2 means or what BIG THETA O(n) means. It's been a long while since I worked with this stuff, and I don't remember learning about BIG THETA or O^2. Otherwise, I agree that T(n) = O(n), assuming your nonrecursive formula is correct.
 
  • #3
The recurrence system part I didn't include was T(0) = 4.

Thanks,
 

1. What does it mean to classify T(n) as O(f(n))?

Classifying T(n) as O(f(n)) means that the time complexity of an algorithm or function, represented by T(n), is bounded by the growth rate of another function, represented by f(n). In other words, f(n) is an upper bound on the time complexity of T(n).

2. What is the significance of classifying T(n) as O(f(n))?

Classifying T(n) as O(f(n)) allows us to analyze the efficiency of an algorithm or function in terms of its input size. It helps us understand how the time required to run the algorithm or function increases as the input size grows. This information is crucial in designing efficient algorithms and optimizing their performance.

3. How is the big O notation used in classifying T(n) as O(f(n))?

The big O notation is used to represent the upper bound or worst-case scenario of an algorithm or function's time complexity. In the context of classifying T(n) as O(f(n)), the big O notation is used to compare the growth rate of T(n) with that of f(n) and determine if T(n) is bounded by f(n).

4. What is the difference between O(n) and O(n2)?

O(n) represents a linear growth rate, where the time complexity of an algorithm or function increases proportionally with the input size. O(n2) represents a quadratic growth rate, where the time complexity increases exponentially with the input size. In other words, an algorithm with a time complexity of O(n2) will take much longer to run than an algorithm with a time complexity of O(n) for large input sizes.

5. Can T(n) be classified as multiple big O notations?

Yes, T(n) can be classified as multiple big O notations, as long as it is bounded by those functions. For example, if T(n) is bounded by both O(n) and O(n2), it can be classified as O(n) and O(n2). This is because the big O notation only represents the upper bound, and T(n) can have multiple possible upper bounds.

Similar threads

Comp Sci Proofing Big-O Notation: O(max(f(n), g(n)))
    • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
Comp Sci Big O/Little O, Big Ω, little ω
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
B Why is Big-O about how rapidly the Taylor graph approaches that of f(x)?
    • Calculus
Replies
19
Views
2K
Algorithm for computing the depths of all the nodes of tree
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Force Required to Stretch a Rubber Band to a Certain Diameter
    • Engineering and Comp Sci Homework Help
Replies
8
Views
3K
Question about wording of an algorithm-complexity problem
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Language that cannot be decided by a TM using space O(log n)
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Understanding Big Oh: Exploring the Best Function for a Given Equation
    • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
Solving recurence T(n)=T(n-1)+O(n lg n)
    • Engineering and Comp Sci Homework Help
Replies
1
Views
5K
Find Velocity of the wooden block at t=4 sec
    • Introductory Physics Homework Help
Replies
10
Views
2K

Hot Threads

Recent Insights

Back
Top