What is 45 like between these two towns?
Since 45 doesn't go to Jackson, MS, I presume you mean Jackson, TN? If so, US 45 is 4-lanes the whole way, though it takes a turn at Selmer, TN and there are several segments in Tennesse that are undivided, lower speed limit, and NUMEROUS driveways.
Sorry I meant down to Interstate 20 Is it still 4 lanes there
Yes (if you follow US 45 Alternate), but if you're going to Jackson turn off near Starkville and take MS 25.
If you're talking about using US 45 to get from Tupelo to Jackson, MS then it would only be the first part of your route. At Columbus, you would want to take US 82 West to Starkville, then MS 25 South to Jackson.
That's an entirely 4-laned and mostly pleasant route. However, it is not going to save you much time, if any, over using the Natchez Trace.
If you go by the Natchez Trace Parkway you should run into I-20 west of Clinton. But if you want to Go to Jackson go I-55 South to Jackson from the Natchez Trace.
As for Going Hwy 45 from Tupelo It is all 4 lane except a place through West Point but though there this is still kinda 4-Lane as 45 Alt but it is like the main stretch through town. Hwy 82 is to Interstate standards to a little past Starkville going west. Where 25 connects it is 4-Lane all the way from Starkville to Jackson. The only place where it is not like the Interstate is at Louisville where there is a 4-Way stop with an Exxon and an eatery and with Walmart close by. This is the only break until you get west of Carthage. From Carthage to North of Brandon it is like 45 and 45 Alt with county road turnoffs. From north of Brandon to Jackson, 25 is Lakeland Dr. and is one of the main suburban stretches in NE Rankin County all the way to I-55. A lot of red lights and establishments along the way. Before you get to Jackson, there is a stretch of Hwy that goes from Lakeland Dr (MS 25) by the Airport to Hwy 80 at a stop light and you keep going a few blocks from Hwy 80 you get to I-20. Otherwise you will get to I-55 and go south to the Stack and I -20
Hope that helps
richllewis is correct. I forgot about 45-Alt. You would indeed want to keep to 45-Alt South at Shannon, then go west at the 82 interchange near Starkville. That will save you quite a bit of time. Have a look at this map (http://mdot.ms.gov/documents/planning/Maps/State%20Highway%20Maps/Statewide%20Map-%20Front%20Side.pdf) before you set out.
Although the highway is undivided through West Point, all four lanes are maintained through that segment.